Reading the Answer Back
Dynamic Programming: lesson 19 of 20
The table holds the score; walking it backwards holds the answer.
Lesson 19 of 20 · 6 min
Reading the Answer Back
Step 1 of 7
The table is already filled, and the corner says 4. That is the score. It does not say which four letters.
The Idea
A DP table answers "how good", not "which". But each cell was decided by one specific neighbour, so start at the final cell and ask which one. Matching characters mean a diagonal step and a recorded letter; otherwise follow the larger neighbour. The walk costs O(n + m) on a table you already paid for.
Real-World Example
A code review diff. Nobody wants the number 4 — they want the lines that survived unchanged. The viewer fills the same table an edit-distance check would, then retraces it to mark which lines moved, which were added and which stayed.
The Code
a, b = "night", "eight"
best = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
best[i][j] = (best[i - 1][j - 1] + 1 if a[i - 1] == b[j - 1]
else max(best[i - 1][j], best[i][j - 1]))
i, j, out = len(a), len(b), []
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1]) # a match: step diagonally
i, j = i - 1, j - 1
elif best[i - 1][j] >= best[i][j - 1]:
i -= 1 # follow the cell that fed it
else:
j -= 1
print(best[-1][-1], "".join(reversed(out))) # 4 ightYour turn
What does this print?
best = [[0, 0, 0],
[0, 1, 1],
[0, 1, 1]]
a, b = "xy", "xz"
i, j, out = 2, 2, []
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif best[i - 1][j] >= best[i][j - 1]:
i -= 1
else:
j -= 1
print("".join(reversed(out)))Mini quiz
1 / 3