Loading...
String manipulation and sequence comparison are where DP truly shines. Master the classic patterns that power tools like `diff`, `spell-check`, and DNA sequencing.
Finding the longest part of a sequence that increments. The catch: The elements don't have to be contiguous.
State: `dp[i]` = length of LIS ending exactly at index `i`.
The O(n^2) version is easy. To reach O(n log n), you use a "Tails" array and Binary Search.
1function LIS(arr):2 n = len(arr)3 dp = array(n, 1) // Base case: length 14 5 for i from 0 to n-1:6 for j from 0 to i-1:7 if arr[j] < arr[i]:8 dp[i] = max(dp[i], dp[j] + 1)9 10 return max(dp)LCS finds the longest sequence that appears in both strings in the same order. Edit the strings below and watch the 2D table fill according to the match/no-match logic.
| B | D | C | A | B | A | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
dp[i][j] = (a[i] == b[j])
? 1 + dp[i-1][j-1]
? max(dp[i-1][j], dp[i][j-1])
To find the actual string, start from the bottom-right cell. If the characters match, move diagonally. If they don't, move towards the larger neighbor (Top or Left).
How many Insert, Delete, or Replace operations do you need to turn String A into String B? This is the Levenschtein Distance.
1for i from 1 to n:2 for j from 1 to m:3 if a[i] == b[j]:4 dp[i][j] = dp[i-1][j-1]5 else:6 dp[i][j] = 1 + min(7 dp[i][j-1], // Insert8 dp[i-1][j], // Delete9 dp[i-1][j-1] // Replace10 )