AdvancedDynamic Programming
2-D DP: a grid of subproblems
For two strings, dp[i][j] = the answer for the first i chars of one and the first j of the other. Each cell looks left, up and diagonally.
The idea
With two sequences, the subproblem is a pair of prefixes. Lay them out as a grid: row i is a prefix of the first string, column j a prefix of the second. Each cell is built from its neighbours.
Longest common subsequence: if the last characters match, take the diagonal + 1; otherwise take the better of dropping one character from either string.
Worked example
LCS of “abcde” and “ace”
- a = a → diagonal + 1 → 1
- c = c later → builds to 2; e = e → 3
- The bottom-right cell is 3 (“ace”).
In code (Python)
def lcs(a, b):
rows, cols = len(a) + 1, len(b) + 1
dp = [[0] * cols for _ in range(rows)]
for i in range(1, rows):
for j in range(1, cols):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]O(m·n) time and space (O(min(m, n)) space with two rows).
How to spot it
- Two strings or arrays: common subsequence, edit distance, interleaving. Also grid paths (unique paths).
Common mistakes
- Off-by-one between dp indices (prefix lengths) and string indices (i − 1).
- Building the grid with [[0]*cols]*rows, which repeats the same row object.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →