2-D Dynamic Programming
A grid of subproblems, each filled from its neighbours.
- Brute force
- O(2ⁿ · m) — enumerate subsequences or paths
- With the pattern
- O(m · n) — each cell filled once in O(1)
- Extra space
- O(m · n), or O(min(m, n)) with row compression
In plain English
“Two friends compare their travel diaries to find the longest list of cities they both visited in the same order. They fill a chart: each square answers "using my first i entries and your first j entries, how long is our shared list?" Each square is filled by glancing at the squares just above, left or diagonally up-left.”
Why it's fast
Comparing two sequences by brute force means trying all 2ⁿ subsequences of one against the other. But every question shrinks to a prefix pair (i, j), and there are only m × n such pairs. Each cell is O(1) from its neighbours: on a match, dp[i-1][j-1] + 1; otherwise the better of dropping a char from either side.
Spot it when the problem says…
- two strings / two sequences
- longest common subsequence
- minimum edits to convert
- number of unique paths in a grid
- palindromic subsequence (i..j ranges)
- match with wildcards / regex
Visualize
Longest common subsequence
Length of the longest sequence of characters appearing in order (not necessarily adjacent) in both strings.
| ∅ | B | D | C | A | B | |
|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | |||||
| B | 0 | |||||
| C | 0 | |||||
| B | 0 | |||||
| D | 0 | |||||
| A | 0 |
Row/column 0 = an empty string: LCS with nothing is 0. dp[i][j] = LCS of a[:i] and b[:j].
1def lcs(a, b):2 m, n = len(a), len(b)3 dp = [[0] * (n + 1) for _ in range(m + 1)]4 for i in range(1, m + 1):5 for j in range(1, n + 1):6 if a[i - 1] == b[j - 1]:7 dp[i][j] = dp[i - 1][j - 1] + 1 # extend the match8 else:9 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])10 return dp[m][n]How to apply it
- 01Define
dp[i][j]over prefixes (s[:i],t[:j]) or a range (s[i..j]). - 02Add an extra row/column for empty prefixes so base cases are simple.
- 03Write the transition: what happens when
s[i-1] == t[j-1], and when it doesn't. - 04Fill rows top-to-bottom, columns left-to-right (or by increasing length for ranges).
- 05Optionally compress to one or two rows since each row only needs the previous one.
Variations you'll meet
Longest Common Subsequence
The visualizer's example: match → diagonal + 1, else max of up and left.
def longest_common_subsequence(a: str, b: str) -> int: m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): 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[m][n]Edit Distance
Mismatch costs 1 + min(insert, delete, replace) = left, up, diagonal. Base row/column are 0..n and 0..m.
def min_distance(a: str, b: str) -> int: m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[m][n]Grid paths
Unique Paths / Minimum Path Sum: dp[r][c] from top and left neighbours; compresses to one row.
Interval DP
dp[i][j] over a substring range, filled by increasing length (Longest Palindromic Subsequence).
Common mistakes
- Index confusion between
dp[i][j]ands[i-1]when using the extra empty-prefix row. - Building the table with
[[0] * n] * m— every row is the same list object. - Forgetting to initialise the first row/column (edit distance needs 0..n, not zeros).
- Filling interval DP row-by-row instead of by increasing length, reading cells not yet computed.
- Row compression that overwrites
dp[j-1]from the previous row before using it as the diagonal.
Practice ladder
Easy → hard. Tick them off as you go.
Think you've got it?
Let the AI interviewer throw a 2-D Dynamic Programming problem at you and grade how you explain it.