alignment DP
Summary
Top-down
Solve(i, j):
if i == n + 1 or j == m + 1:
return BASE(i, j)
if Memo[i, j] != UNSEEN:
return Memo[i, j]
answer = IDENTITY
for each option o in OPTIONS(i, j):
(ni, nj) = NEXT(i, j, o)
candidate = STEP(i, j, o, Solve(ni, nj))
answer = COMBINE(answer, candidate)
Memo[i, j] = answer
return answer
return Solve(1, 1)
Bottom-up
Initialize DP[n + 1, j] and DP[i, m + 1]
for i = n down to 1:
for j = m down to 1:
DP[i, j] = IDENTITY
for each option o in OPTIONS(i, j):
(ni, nj) = NEXT(i, j, o)
candidate = STEP(i, j, o, DP[ni, nj])
DP[i, j] = COMBINE(DP[i, j], candidate)
return DP[1, 1]
Concept
Longest Common Subsequence
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| Skip | Take the maximum of |
base cases
option 1
take a_i and b_j
if equal
else
option 2
ignore a_i
val_2 = C(i+1, j)
option 3
ignore b_j
val_3 = C(i, j+1)
combine
C(i, j) = max{val_1, val_2, val_3}
Edit Distance
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| Delete |
D(i, j) = edit distance between a_i,…,a_n and b_j,…,b_m
base cases
D(i, m + 1) - end of 2nd string = n - i + 1
D(n + 1, j) - end of 1st string = m - j + 1
option 1
align a_i and b_j
val_1 = D(i + 1, j + 1) if a_i = b_j else D(i + 1, j + 1) + 1
option 2
delete a_i
val_2 = D(i + 1, j) + 1
option 3
add b_j
val_2 = D(i, j + 1) + 1
combine
D(i, j) = min{val_1, val_2, val_3}