Chapter 22 — Dynamic Programming (2D & Advanced)
Chapter 22 — Dynamic Programming (2D & Advanced)
Hey everyone! Welcome back to Namaste DSA!
In Chapter 21 our DP state was a single number (dp[i]). Many problems need two dimensions — a grid, or two strings being compared. The idea is identical; the table just becomes 2D. Once you can fill a DP table by hand, these problems become mechanical.
What we will cover:
- Grid DP — unique paths & min path sum
- The Knapsack pattern
- Longest Common Subsequence (LCS)
- Edit distance
- Building the DP table by hand
- Interview Questions
1. Grid DP — Unique Paths
How many ways to go from top-left to bottom-right of an m×n grid, moving only right or down? To reach any cell you came from above or from the left: dp[i][j] = dp[i-1][j] + dp[i][j-1].
Fill the table (each cell = ways to reach it):
1 1 1 1
1 2 3 4
1 3 6 10 ← bottom-right = 10 paths
Top row & left column are all 1 (only one way along an edge).
Every other cell = cell above + cell to the left.
function uniquePaths(m, n) {
const dp = Array.from({length: m}, () => new Array(n).fill(1));
for (let i = 1; i < m; i++)
for (let j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}
Min path sum is the same shape — replace + with cell + min(up, left).
2. The Knapsack Pattern
Given items with weights and values and a capacity W, maximize value without exceeding W. For each item you make a binary choice: take it or skip it.
function knapsack(weights, values, W) {
const n = weights.length;
const dp = Array.from({length: n+1}, () => new Array(W+1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w]; // skip item i
if (weights[i-1] <= w) { // can we take it?
dp[i][w] = Math.max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1] // take it
);
}
}
}
return dp[n][W];
}
// O(n·W)
Knapsack is the template for dozens of "subset with a constraint" problems (partition equal subset, coin change, target sum...).
3. Longest Common Subsequence (LCS)
Longest subsequence present in both strings (order kept, gaps allowed — remember Chapter 03). Compare characters: if they match, extend the diagonal; if not, take the best of dropping one character from either string.
dp[i][j] = LCS of a[0..i-1] and b[0..j-1] if a[i-1] === b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (match → diagonal+1) else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
a = "ABCBDAB", b = "BDCAB" → LCS length = 4 ("BCAB")
"" 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
... (fill row by row → bottom-right = 4)
function lcs(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = a[i-1] === b[j-1]
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}
4. Edit Distance
Minimum insert/delete/replace operations to turn string A into string B. Same 2D table; at each cell take the cheapest of the three operations.
if a[i-1] === b[j-1]: dp[i][j] = dp[i-1][j-1] (no op needed)
else: dp[i][j] = 1 + min(
dp[i-1][j], // delete
dp[i][j-1], // insert
dp[i-1][j-1] // replace
)
5. Building the DP Table by Hand
┌─────────────────────────────────────────────────────────────┐ │ HOW TO SOLVE ANY 2D DP │ ├─────────────────────────────────────────────────────────────┤ │ 1. Draw the grid; label rows & columns with the inputs │ │ 2. Fill the base cases (first row / first column) │ │ 3. Find the relation: each cell from its neighbors │ │ (up, left, diagonal) │ │ 4. Fill in order so dependencies are ready │ │ 5. Answer is usually the bottom-right cell │ └─────────────────────────────────────────────────────────────┘
Interview Questions — Quick Fire!
Q: How is 2D DP different from 1D DP?
"Only in the number of dimensions of the state. 1D DP indexes by one variable like position; 2D DP indexes by two — such as a grid cell (row, col) or a pair of string indices (i, j). The method is the same: define the state, write the relation in terms of smaller states, set base cases, and fill in dependency order."
Q: Explain the unique-paths recurrence.
"dp[i][j] is the number of ways to reach cell (i, j) moving only right or down. You can only arrive from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. The first row and column are all 1 since there's a single path along an edge. It's O(m·n)."
Q: What's the knapsack recurrence?
"For each item you either skip it, keeping dp[i-1][w], or take it if it fits, giving dp[i-1][w - weight] + value. dp[i][w] is the max of those. It's the canonical 'choose a subset under a constraint' template, running in O(n·W)."
Q: How does the LCS recurrence work?
"Comparing prefixes: if the current characters match, the LCS extends the diagonal cell by one, dp[i-1][j-1] + 1. If they don't match, you take the better of ignoring one character from either string, max(dp[i-1][j], dp[i][j-1]). The answer is the bottom-right cell, in O(m·n)."
Q: Why fill the DP table in a specific order?
"Because each cell depends on previously computed cells — usually up, left, or diagonal. You must fill those before the cell that needs them, which is why you typically iterate rows top-to-bottom and columns left-to-right after seeding the base cases."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| 2D state | dp[i][j] — grid cell or two string indices. |
| Unique paths | dp[i][j] = up + left. |
| Knapsack | Take or skip; O(n·W). |
| LCS | Match → diagonal+1, else max(up, left). |
| Edit distance | 1 + min(insert, delete, replace). |
| Method | Base cases → relation → fill in order. |
What's Next?
Chapter 23: Bit Manipulation — working with the raw 1s and 0s for blazing-fast tricks like finding the single number with XOR.
Keep coding, keep grinding! See you in the next one!
Post a Comment