Chapter 21 — Dynamic Programming (1D)
Chapter 21 — Dynamic Programming (1D)
Hey everyone! Welcome back to Namaste DSA!
Dynamic Programming (DP) is the topic that scares people the most — but here's the secret: DP is just recursion that remembers its answers. If a problem has overlapping subproblems (it recomputes the same things), DP stores those answers and reuses them. Let's demystify it slowly.
What we will cover:
- The two signals a problem is DP
- Memoization (top-down) vs Tabulation (bottom-up)
- Fibonacci: O(2ⁿ) → O(n)
- Climbing stairs
- House robber
- How to FIND the recurrence
- Interview Questions
1. The Two Signals of DP
┌─────────────────────────────────────────────────────────────┐ │ A problem is DP if it has BOTH: │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 1. OVERLAPPING SUBPROBLEMS │ │ → the same smaller problem is solved again and again │ │ (like fib(3) computed many times) │ │ │ │ 2. OPTIMAL SUBSTRUCTURE │ │ → the best answer is built from the best answers │ │ of subproblems │ │ │ └─────────────────────────────────────────────────────────────┘
2. Memoization vs Tabulation
| Memoization (Top-Down) | Tabulation (Bottom-Up) | |
|---|---|---|
| Style | Recursion + a cache | Loop + a table |
| Direction | Start big, break down | Start small, build up |
| Pros | Closer to natural recursion | No recursion/stack overflow |
3. Fibonacci — The "Hello World" of DP
Naive recursion is O(2ⁿ) because it recomputes the same subproblems (Chapter 05). DP fixes that.
// MEMOIZATION (top-down) — O(n)
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n]; // reuse!
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}
// TABULATION (bottom-up) — O(n), O(1) space possible
function fibTab(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr]; // only keep last two
}
return curr;
}
WHY MEMO TURNS O(2ⁿ) INTO O(n): Without memo: fib(5) tree has ~2⁵ nodes (lots of repeats). With memo: each fib(k) computed ONCE, then cached. n unique subproblems × O(1) each = O(n).
4. Climbing Stairs
You can climb 1 or 2 steps at a time. How many ways to reach step n? To reach step n you came from step n-1 (one step) or n-2 (two steps) — so ways(n) = ways(n-1) + ways(n-2). It's Fibonacci in disguise!
function climbStairs(n) {
let oneBack = 1, twoBack = 1;
for (let i = 2; i <= n; i++) {
[twoBack, oneBack] = [oneBack, oneBack + twoBack];
}
return oneBack;
}
5. House Robber
Rob houses for max money, but you can't rob two adjacent houses. At each house, choose: rob it (money + best up to i-2) or skip it (best up to i-1).
function rob(nums) {
let prev = 0, prev2 = 0; // best up to i-1 and i-2
for (const money of nums) {
const take = prev2 + money; // rob this house
const skip = prev; // skip this house
prev2 = prev;
prev = Math.max(take, skip); // best so far
}
return prev;
}
HAND TRACE: rob([2, 7, 9, 3, 1]) house 2: max(0+2, 0)=2 prev2=0 prev=2 house 7: max(0+7, 2)=7 prev2=2 prev=7 house 9: max(2+9, 7)=11 prev2=7 prev=11 house 3: max(7+3, 11)=11 prev2=11 prev=11 house 1: max(11+1, 11)=12 prev2=11 prev=12 answer = 12 (rob houses 2, 9, 1) ✔
6. How to FIND the Recurrence (The Real Skill)
┌─────────────────────────────────────────────────────────────┐ │ A 4-STEP RECIPE FOR ANY DP │ ├─────────────────────────────────────────────────────────────┤ │ 1. STATE — what does dp[i] MEAN? │ │ (e.g. "max money using houses 0..i") │ │ 2. CHOICE — at each step, what are my options? │ │ (rob it / skip it) │ │ 3. RELATION— write dp[i] using smaller dp[...] │ │ dp[i] = max(dp[i-1], dp[i-2] + nums[i]) │ │ 4. BASE — the smallest cases (dp[0], dp[1]) │ └─────────────────────────────────────────────────────────────┘
Master this recipe and DP stops being scary — every problem becomes "define the state, list the choices, write the relation."
Interview Questions — Quick Fire!
Q: What makes a problem solvable by DP?
"Two properties: overlapping subproblems, meaning the same smaller problems recur, and optimal substructure, meaning the optimal answer is built from optimal answers to subproblems. If both hold, you can cache subproblem results and reuse them."
Q: What's the difference between memoization and tabulation?
"Memoization is top-down: you write the natural recursion and cache results to avoid recomputation. Tabulation is bottom-up: you fill a table iteratively from the base cases. Memoization is intuitive; tabulation avoids recursion overhead and stack-overflow risk, and often allows space optimization."
Q: How does DP turn Fibonacci from O(2ⁿ) into O(n)?
"Naive Fibonacci recomputes the same subproblems exponentially often. By caching each fib(k) the first time it's computed, every subproblem is solved exactly once — n unique subproblems times O(1) work each gives O(n). You can even drop to O(1) space by keeping only the last two values."
Q: Walk me through the House Robber recurrence.
"State dp[i] is the max money robbing among the first i houses. At house i you either rob it — adding its money to dp[i-2] since you skip the adjacent house — or skip it, keeping dp[i-1]. So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). It runs in O(n) time and O(1) space with two rolling variables."
Q: What's your process for finding a DP recurrence?
"Define the state clearly — what dp[i] represents. Identify the choices available at each step. Express dp[i] in terms of smaller states based on those choices. Then nail the base cases. State, choice, relation, base."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| DP = | Recursion + remembering answers. |
| Two signals | Overlapping subproblems + optimal substructure. |
| Memoization | Top-down recursion + cache. |
| Tabulation | Bottom-up table. |
| Recipe | State → Choice → Relation → Base. |
What's Next?
Chapter 22: Dynamic Programming (2D) — grids, knapsack, and longest common subsequence, where the DP table becomes two-dimensional.
Keep coding, keep grinding! See you in the next one!
Post a Comment