-
Notifications
You must be signed in to change notification settings - Fork 0
027 — 2D Dynamic Programming
The Arrays and Strings chapter covered the data structure itself — an indexable sequence, extended here into a 2-D memo table. This chapter is about recognizing when a problem's state genuinely needs two independent indices, not one, so the table you fill has to be an array of arrays rather than a single array.
Picture two editors comparing drafts of the same document line by line, trying to find the longest sequence of sentences that appears in both drafts, in the same relative order (even if other sentences were inserted or deleted in between). Neither editor can just eyeball it — the answer to "how much do drafts A and B agree on through sentence i of A and sentence j of B?" depends on three smaller sub-answers: how much they agreed through i-1 and j, through i and j-1, and through i-1 and j-1. You'd naturally build a grid with draft A's sentences down one side and draft B's along the other, filling it cell by cell, where each cell's value only ever depends on the cell above it, the cell to its left, and the cell diagonally above-left. That grid — two sequences, one on each axis, a table filled by referencing your immediate neighbors — is the shape of 2-D dynamic programming.
Reach for 2-D DP when you see:
- Two sequences (strings or arrays) being compared, with a question like "longest common subsequence," "edit distance," "is one a subsequence/interleaving of the other" — the natural state is "how far have I gotten through sequence A, and how far through sequence B," which is inherently two independent indices, hence a 2-D table.
- "Edit distance" specifically — "minimum number of insertions/deletions/substitutions to turn one string into another" — is close to the canonical 2-D DP problem; each cell represents the cost to convert one prefix into another.
- Grid path-counting or grid path-cost problems — "number of unique paths from top-left to bottom-right," "minimum path sum through a grid," where you can only move right or down — the grid itself is already 2-D, and each cell's answer depends on the cell above and the cell to the left.
-
A single sequence but with an extra dimension of state — "longest palindromic substring" (indexed by a start
iand endj), or "knapsack" problems (indexed by "item index" and "remaining capacity") — even without two separate input sequences, the state needs two numbers to describe "where am I," which is the real tell.
The unifying tell: describing "how far along am I" takes two indices, not one — whether that's two separate sequences, or one sequence plus a second dimension like capacity or a start/end pair — so the DP table is naturally a grid, and each cell depends on a small number of neighboring cells (typically up, left, and/or diagonal).
Filling a 2-D DP table for Longest Common Subsequence between "ABCBDAB" and "BDCAB" — each cell either extends a diagonal match or takes the best of its neighbors:
"" B D C A B
"" 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4 <- answer: LCS length = 4 ("BCAB")
rule per cell (i, j), comparing s1[i-1] and s2[j-1]:
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (diagonal + 1, chars matched)
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (best of up / left)
func twoDimensionalDPTemplate(_ s1: [Character], _ s2: [Character]) -> Int {
let m = s1.count
let n = s2.count
guard m > 0 && n > 0 else { return 0 } // 🔧 Fill in: base case when one sequence is empty
// dp[i][j] = the answer considering the first i characters of s1
// and the first j characters of s2.
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
// Base row/column — 🔧 Fill in: what does "0 characters of one sequence" mean for this problem?
// (For LCS, dp[0][*] and dp[*][0] are already 0 by initialization — nothing to add.)
for i in 1...m {
for j in 1...n {
if s1[i - 1] == s2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1 // 🔧 Fill in: the "characters match" case
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) // 🔧 Fill in: the "no match" case
}
}
}
return dp[m][n] // 🔧 Fill in: return whatever the problem actually asks for
}Longest Common Subsequence — given two strings text1 and text2, return the length of their longest common subsequence (a sequence that appears in both, in order, not necessarily contiguous). Return 0 if there is none.
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
let s1 = Array(text1)
let s2 = Array(text2)
let m = s1.count
let n = s2.count
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
guard m > 0 && n > 0 else { return 0 }
for i in 1...m {
for j in 1...n {
if s1[i - 1] == s2[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]
}
// smoke test
print(longestCommonSubsequence("abcde", "ace")) // 3 ("ace")
print(longestCommonSubsequence("abc", "abc")) // 3
print(longestCommonSubsequence("abc", "def")) // 0
print(longestCommonSubsequence("ABCBDAB", "BDCAB")) // 4 ("BCAB" or "BDAB")This is the template with the base case filled in — dp[i][0] and dp[0][j] are both 0 (zero characters of either string means zero shared subsequence length, which Array(repeating:count:) already initializes to). The two branches are exactly the diagonal-match-or-best-neighbor rule from the diagram: a character match extends the diagonal cell's answer by one, and a mismatch just inherits the better of "drop the current character of s1" (look up) or "drop the current character of s2" (look left).
2-D DP is the two-editors-comparing-drafts grid — whenever "where am I" takes two numbers to describe, build a table and fill each cell from its up/left/diagonal neighbors.
"Edit Distance" (minimum insert/delete/replace operations to turn word1 into word2) uses the same m x n grid shape as Longest Common Subsequence, but the recurrence for a mismatch at (i, j) is different — it takes the minimum of three neighboring cells, not two, and adds 1 regardless. Which three neighboring cells are those, and what real-world edit (insert, delete, or replace) does each one correspond to?