DPDynamic Programming
Longest Common Subsequence
Find the longest subsequence shared by two sequences using a 2D table over prefix pairs.
| B | D | C | A | B | A | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | · | · | · | · | · | · |
| B | 0 | · | · | · | · | · | · |
| C | 0 | · | · | · | · | · | · |
| B | 0 | · | · | · | · | · | · |
| D | 0 | · | · | · | · | · | · |
| A | 0 | · | · | · | · | · | · |
| B | 0 | · | · | · | · | · | · |
1/44Row 0 and column 0 represent an empty prefix, whose LCS with anything is 0.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Longest Common Subsequence →
1dp[0][*] = dp[*][0] = 02for i in 1 .. m: for j in 1 .. n:3 if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 14 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])5traceback from dp[m][n]Variables
m7
n6
Complexity
best O(n·m)
avg O(n·m)
worst O(n·m)
space O(min(n, m))
Speed