Dynamic programming has a reputation problem. Say “dynamic programming” in a room full of developers and watch half of them wince. It's the topic people skip in textbooks, the category they filter out on LeetCode, the interview subject that triggers cold sweats. DP has this aura of being some elite, math-heavy, galaxy-brain technique reserved for competitive programmers and PhD students. Here's the thing: **that reputation is completely undeserved**. The core idea behind dynamic programming is so simple you'll be annoyed nobody explained it to you sooner. Ready? Here it is: > **If you've already solved a subproblem, don't solve it again.** That's it. That's the whole idea. Everything else is details. The name itself is misleading. “Dynamic programming” doesn't have anything to do with writing code. The word **“programming”** here comes from mathematics, where it means **“filling in a table”** (like “linear programming” or “integer programming”). The “dynamic” part was actually chosen by mathematician Richard Bellman in the 1950s partly because it sounded impressive and would help him get funding. Seriously. The name is marketing, not a description. So forget the intimidating name. What you're about to learn is a **thinking technique** — a way to take a slow, repetitive brute-force solution and make it fast by remembering work you've already done. It's like the difference between recalculating `2 + 2` every time versus just remembering the answer is `4`. By the end of this guide, you'll: - Understand the **core idea** behind dynamic programming (it's one sentence) - Know the difference between **memoization** (top-down) and **tabulation** (bottom-up) - Have a **5-step framework** for solving any DP problem - **Recognize** DP problems on sight - Walk through **six classic beginner problems** with full solutions in TypeScript - Understand **1D vs 2D DP** and **space optimization** - Know the difference between **DP and greedy** - Have a **cheat sheet** you can reference any time No math degree required. Let's go. --- ## The Core Idea: Don't Solve the Same Problem Twice Let's start with the most classic example in all of computer science: the **Fibonacci sequence**. ``` 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... ``` Each number is the sum of the two before it: ``` fib(0) = 0 fib(1) = 1 fib(n) = fib(n - 1) + fib(n - 2) for n ≥ 2 ``` Simple, right? Let's write it in TypeScript: ```typescript function fib(n: number): number { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } ``` Clean. Elegant. **Catastrophically slow.** ### The Explosion: Why Naive Recursion Fails Let's trace what happens when we call `fib(5)`: ``` fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0) ``` Count the calls: | Function call | Times computed | |---------------|---------------| | `fib(5)` | 1 | | `fib(4)` | 1 | | `fib(3)` | **2** | | `fib(2)` | **3** | | `fib(1)` | **5** | | `fib(0)` | **3** | | **Total** | **15 calls** | `fib(5)` makes **15 function calls** to compute the number `5`. That's already wasteful. But watch what happens as `n` grows: | n | Function calls | Result | |-----|----------------|------------| | 5 | 15 | 5 | | 10 | 177 | 55 | | 20 | 21,891 | 6,765 | | 30 | 2,692,537 | 832,040 | | 40 | 331,160,281 | 102,334,155| | 50 | **~40 billion**| 12,586,269,025 | At `fib(50)`, we're making over **40 billion** function calls. On most machines, this would take **minutes or hours**. By `fib(100)`, we'd be looking at more calls than there are **atoms in the observable universe**. The time complexity is **O(2^n)** — exponential. Every increment of `n` roughly doubles the work. This is the definition of a solution that doesn't scale. ### The Problem: Redundant Work Look at the recursion tree again. `fib(3)` is computed **twice**. `fib(2)` is computed **three times**. These are the **overlapping subproblems** — the exact same computations being performed over and over again. ``` fib(5) / \ fib(4) fib(3) ← computed AGAIN / \ / \ fib(3) fib(2) fib(2) fib(1) ↑ ↑ ↑ REPEAT REPEAT REPEAT ``` Imagine you're a GPS navigating a road trip. You're driving from New York to LA, and along the way you need to calculate the distance from Chicago to Denver. You compute it. Great. Then 10 minutes later, you need it again. Do you recalculate the entire route from scratch? Of course not. You **remember** the answer. That's dynamic programming. **Remember the answers to subproblems so you never solve them twice.** --- ## Memoization (Top-Down DP) The first strategy for eliminating redundant work is called **memoization** (not “memorization” — no ‘r’). The idea is simple: 1. Before solving a subproblem, **check if you've already solved it** 2. If yes, **return the cached result** 3. If no, **solve it, cache the result**, and then return it You still write your code recursively (top-down), but you add a **cache** (also called a **memo**) to store results. ### Fibonacci with Memoization ```typescript function fibMemo(n: number, memo: Map = new Map()): number { if (n <= 1) return n; if (memo.has(n)) return memo.get(n)!; const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); memo.set(n, result); return result; } ``` ### The Pruned Recursion Tree Watch what happens to the recursion tree. Calls that hit the cache are **pruned** — they return instantly instead of branching further: ``` fib(5) / \ fib(4) fib(3) ✓ cached! / \ fib(3) fib(2) ✓ cached! / \ fib(2) fib(1) / \ fib(1) fib(0) ``` Instead of 15 calls, we now make **9 calls** for `fib(5)`. But the real magic shows at scale: | n | Without memo | With memo | Speedup | |-----|-------------|-----------|---------------| | 10 | 177 | 19 | ~9x | | 20 | 21,891 | 39 | ~561x | | 30 | 2,692,537 | 59 | ~45,636x | | 40 | 331,160,281 | 79 | ~4,191,901x | | 50 | ~40 billion | 99 | ~400 million x| With memoization, each value from `fib(0)` to `fib(n)` is computed **exactly once**. The time complexity drops from **O(2^n)** to **O(n)**. The space complexity is **O(n)** for the cache plus **O(n)** for the recursion call stack. > **Key Insight**: Memoization is the easiest upgrade you can make to any recursive solution. If the function takes the same inputs and always returns the same output (it's a **pure function**), you can memoize it. Just add a cache. --- ## Tabulation (Bottom-Up DP) The second strategy flips the approach. Instead of starting at `fib(n)` and recursing down, you **start at the base cases** and **build up** to the answer. This is called **tabulation** because you literally fill in a **table** (array) from left to right, bottom to top. ### Fibonacci with Tabulation ```typescript function fibTab(n: number): number { if (n <= 1) return n; const dp: number[] = new Array(n + 1); dp[0] = 0; dp[1] = 1; for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } ``` ### Watching the Table Fill Let's trace `fibTab(7)`: ``` Index: 0 1 2 3 4 5 6 7 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ │ │ │ │ │ │ ← base cases └────┴────┴────┴────┴────┴────┴────┴────┘ Step 1: dp[2] = dp[1] + dp[0] = 1 + 0 = 1 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ 1 │ │ │ │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ Step 2: dp[3] = dp[2] + dp[1] = 1 + 1 = 2 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ 1 │ 2 │ │ │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ Step 3: dp[4] = dp[3] + dp[2] = 2 + 1 = 3 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ 1 │ 2 │ 3 │ │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ Step 4: dp[5] = dp[4] + dp[3] = 3 + 2 = 5 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ 1 │ 2 │ 3 │ 5 │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ Step 5: dp[6] = dp[5] + dp[4] = 5 + 3 = 8 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ Step 6: dp[7] = dp[6] + dp[5] = 8 + 5 = 13 ┌────┬────┬────┬────┬────┬────┬────┬────┐ dp: │ 0 │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │ 13 │ ✓ answer └────┴────┴────┴────┴────┴────┴────┴────┘ ``` No recursion. No call stack. Just a simple loop filling in values from left to right. **Time complexity**: O(n) — we fill each cell once. **Space complexity**: O(n) — the `dp` array. ### Space Optimization: O(1) Here's the key observation: to compute `dp[i]`, we only need `dp[i - 1]` and `dp[i - 2]`. We don't need the entire table — just the **previous two values**. We can replace the array with two variables: ```typescript function fibOptimized(n: number): number { if (n <= 1) return n; let prev2 = 0; let prev1 = 1; for (let i = 2; i <= n; i++) { const current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } ``` **Time complexity**: O(n). **Space complexity**: O(1) — just two variables. This pattern — **solving the full problem, then optimizing space** — is fundamental in DP. Always get the correct solution first, then worry about space. --- ## Memoization vs Tabulation Both approaches solve DP problems. Both eliminate redundant computation. But they have different trade-offs: | Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) | |---|---|---| | **Approach** | Start from the main problem, recurse to subproblems | Start from the smallest subproblems, build up | | **Implementation** | Recursive + cache | Iterative + table (array) | | **Subproblems computed** | Only those **needed** by the main problem | **All** subproblems up to the target | | **Call stack** | Uses recursion (risk of stack overflow for large n) | No recursion (no stack overflow risk) | | **Space optimization** | Harder (cache retains all computed values) | Easier (can often reduce to O(1) space) | | **Ease of writing** | More intuitive — translate recursion directly | Requires thinking about iteration order | | **Performance** | Slight overhead from function calls and cache lookups | Usually faster in practice (simple loops, cache-friendly) | | **Debugging** | Harder (recursive call chains) | Easier (print the table at each step) | ### When to Use Which **Use memoization when:** - The recursive solution is easy to write - Not all subproblems need to be solved - You're more comfortable thinking top-down - The state space is sparse (many states are unreachable) **Use tabulation when:** - You need to optimize space - You want to avoid stack overflow for large inputs - All subproblems will be needed anyway - You want the most performant solution in practice > **Pro tip**: In interviews, start with memoization (it's faster to write), then mention you could convert to tabulation for better space/performance. In production code, tabulation is usually preferred because it's iterative and easier to reason about. --- ## The DP Framework (5 Steps) Here's a systematic framework you can apply to **any** DP problem. Memorize this. Tattoo it on your arm. Write it on a sticky note. These five steps will guide you through every DP problem you ever encounter. ### Step 1: Define the State What does `dp[i]` (or `dp[i][j]`) represent? This is the **most important step**. If you get this wrong, everything else falls apart. The state definition is a plain English sentence that describes what each entry in your table means. Examples: - Fibonacci: `dp[i]` = the i-th Fibonacci number - Climbing Stairs: `dp[i]` = the number of ways to reach step `i` - House Robber: `dp[i]` = the maximum money you can rob from houses `0` to `i` - Coin Change: `dp[i]` = the minimum number of coins needed to make amount `i` > **Rule of thumb**: The state usually matches what the problem is asking for. If the problem says “find the minimum number of X,” then `dp[i]` = “the minimum number of X for some input i.” ### Step 2: Find the Recurrence Relation How does `dp[i]` relate to previous states? This is the **transition formula** — the equation that tells you how to compute each state from smaller states. This is where the actual logic of the problem lives. Examples: - Fibonacci: `dp[i] = dp[i - 1] + dp[i - 2]` - Climbing Stairs: `dp[i] = dp[i - 1] + dp[i - 2]` - House Robber: `dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])` - Coin Change: `dp[i] = min(dp[i - coin] + 1)` for each coin ### Step 3: Identify Base Cases What are the starting values? What states can you fill in without the recurrence? Every recurrence needs a foundation. Without base cases, you have an infinite recursion or an uninitialized table. Examples: - Fibonacci: `dp[0] = 0`, `dp[1] = 1` - Climbing Stairs: `dp[0] = 1`, `dp[1] = 1` - House Robber: `dp[0] = nums[0]`, `dp[1] = max(nums[0], nums[1])` - Coin Change: `dp[0] = 0` (zero coins needed for amount zero) ### Step 4: Determine Iteration Order For tabulation: which direction do you fill the table? The rule is simple: **by the time you compute `dp[i]`, all states it depends on must already be computed**. - If `dp[i]` depends on `dp[i - 1]` and `dp[i - 2]`, iterate **left to right** (i = 2, 3, 4, ...) - If `dp[i]` depends on `dp[i + 1]`, iterate **right to left** - For 2D DP, think about which cells each cell depends on and fill accordingly For memoization, you don't need to worry about this — recursion handles the order for you. ### Step 5: Optimize Space (if possible) Once you have a working solution, look at which previous states each cell actually needs. If `dp[i]` only depends on `dp[i - 1]`, you don't need the full array — just one variable. If it depends on the previous row in a 2D table, you can reduce from a 2D array to a 1D array. **Always do this step last.** Get the correct answer first, then optimize. --- ## Recognizing DP Problems One of the hardest things about DP is knowing **when** to use it. Here are the signals: ### Signal 1: The Problem Asks for Optimization or Counting Watch for these phrases in the problem statement: - **“How many ways...”** → counting problem → likely DP - **“What is the minimum/maximum...”** → optimization → likely DP - **“Can you reach...” / “Is it possible...”** → feasibility → likely DP - **“What is the longest/shortest...”** → optimization → likely DP ### Signal 2: Overlapping Subproblems When you think about a recursive solution and notice the same inputs appearing multiple times, that's a strong DP signal. We saw this with Fibonacci: `fib(3)` was computed twice in the recursion tree for `fib(5)`. ### Signal 3: Optimal Substructure The optimal solution to the overall problem **contains** optimal solutions to its subproblems. For example, the shortest path from A to C that goes through B must contain the shortest path from A to B and the shortest path from B to C. ### Signal 4: Choices at Each Step At each point in the problem, you have to make a **choice** (take this item or skip it, use this coin or don't, go right or go down), and you need to try all possibilities to find the best one. This is what distinguishes DP from greedy — with greedy, you make a single locally optimal choice. With DP, you **try all choices and pick the best**. ### Quick Checklist ``` □ Is the problem asking for min/max/count/possibility? □ Can I break it into smaller subproblems? □ Do subproblems overlap (same inputs, same outputs)? □ Does the optimal solution contain optimal sub-solutions? □ Do I need to make choices at each step? If 3+ of these are "yes" → almost certainly DP. ``` --- ## Beginner Problem 1: Climbing Stairs (LeetCode 70) This is the **“Hello World”** of dynamic programming. If you can solve this, you can solve DP problems. ### The Problem > You are climbing a staircase. It takes `n` steps to reach the top. Each time you can climb **1 step** or **2 steps**. How many **distinct ways** can you climb to the top? ### Applying the 5-Step Framework **Step 1: Define the state** `dp[i]` = the number of distinct ways to reach step `i`. **Step 2: Find the recurrence relation** To reach step `i`, you either: - Came from step `i - 1` (took 1 step), OR - Came from step `i - 2` (took 2 steps) The total ways to reach step `i` = ways to reach step `i - 1` + ways to reach step `i - 2`: ``` dp[i] = dp[i - 1] + dp[i - 2] ``` Wait — that's the Fibonacci recurrence! Climbing stairs **is** Fibonacci. This is why Fibonacci is taught first. **Step 3: Base cases** - `dp[0] = 1` — there's 1 way to stand at the ground (do nothing) - `dp[1] = 1` — there's 1 way to reach step 1 (take one step) **Step 4: Iteration order** Left to right: `i = 2, 3, 4, ..., n` **Step 5: Space optimization** Each state depends on only the previous two → can optimize to O(1). ### Solution 1: Brute-Force Recursion ```typescript function climbStairsBrute(n: number): number { if (n <= 1) return 1; return climbStairsBrute(n - 1) + climbStairsBrute(n - 2); } ``` **Time**: O(2^n). **Space**: O(n) call stack. Way too slow. ### Solution 2: Memoization (Top-Down) ```typescript function climbStairsMemo( n: number, memo: Map = new Map() ): number { if (n <= 1) return 1; if (memo.has(n)) return memo.get(n)!; const result = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo); memo.set(n, result); return result; } ``` **Time**: O(n). **Space**: O(n). ### Solution 3: Tabulation (Bottom-Up) ```typescript function climbStairsTab(n: number): number { if (n <= 1) return 1; const dp: number[] = new Array(n + 1); dp[0] = 1; dp[1] = 1; for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } ``` **Time**: O(n). **Space**: O(n). ### Solution 4: Space-Optimized ```typescript function climbStairs(n: number): number { if (n <= 1) return 1; let prev2 = 1; let prev1 = 1; for (let i = 2; i <= n; i++) { const current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } ``` **Time**: O(n). **Space**: O(1). This is the optimal solution. ### Tracing Through: n = 5 ``` Step 0: 1 way (stand still) Step 1: 1 way (1) Step 2: 2 ways (1+1, 2) Step 3: 3 ways (1+1+1, 1+2, 2+1) Step 4: 5 ways (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2) Step 5: 8 ways ``` > **Takeaway**: Climbing stairs is literally Fibonacci. Once you recognize that, the problem becomes trivial. Pattern recognition is half the battle in DP. --- ## Beginner Problem 2: Min Cost Climbing Stairs (LeetCode 746) Now let's add a twist: each step has a **cost**. ### The Problem > Given an integer array `cost` where `cost[i]` is the cost of the i-th step, find the **minimum cost** to reach the top of the floor. You can start from step 0 or step 1, and at each step you can climb 1 or 2 steps. ### Applying the 5-Step Framework **Step 1: Define the state** `dp[i]` = the minimum cost to reach step `i`. **Step 2: Recurrence relation** To reach step `i`, you either came from `i - 1` or `i - 2`. You pay the cost of whichever step you came from: ``` dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) ``` **Step 3: Base cases** - `dp[0] = 0` — no cost to stand at step 0 (before starting) - `dp[1] = 0` — no cost to stand at step 1 (before starting) We can start from either step 0 or step 1 for free. The cost is paid when we **leave** a step. **Step 4: Iteration order** Left to right: `i = 2, 3, ..., n` (where `n = cost.length`, the step beyond the last). **Step 5: Space optimization** Only depends on previous two states → O(1). ### Tabulation Solution ```typescript function minCostClimbingStairs(cost: number[]): number { const n = cost.length; const dp: number[] = new Array(n + 1); dp[0] = 0; dp[1] = 0; for (let i = 2; i <= n; i++) { dp[i] = Math.min( dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2] ); } return dp[n]; } ``` ### Space-Optimized Solution ```typescript function minCostClimbingStairsOpt(cost: number[]): number { let prev2 = 0; let prev1 = 0; for (let i = 2; i <= cost.length; i++) { const current = Math.min( prev1 + cost[i - 1], prev2 + cost[i - 2] ); prev2 = prev1; prev1 = current; } return prev1; } ``` **Time**: O(n). **Space**: O(1). ### Trace: cost = [10, 15, 20] ``` Reaching "top" (index 3, beyond the array): dp[0] = 0 dp[1] = 0 dp[2] = min(dp[1] + cost[1], dp[0] + cost[0]) = min(0 + 15, 0 + 10) = 10 dp[3] = min(dp[2] + cost[2], dp[1] + cost[1]) = min(10 + 20, 0 + 15) = 15 Answer: 15 (start at step 1, pay 15, jump two steps to the top) ``` --- ## Beginner Problem 3: House Robber (LeetCode 198) This problem introduces the **“decision at each step”** pattern, which is the bread and butter of DP. ### The Problem > You are a professional robber planning to rob houses along a street. Each house has a certain amount of money. **Adjacent houses have connected security systems** — if two adjacent houses are robbed, the alarm goes off. Find the **maximum amount** you can rob without triggering an alarm. ### The Decision Tree At each house, you have two choices: **rob it** or **skip it**. If you rob house `i`, you can't rob house `i - 1`. If you skip it, you move on. ``` Houses: [2, 7, 9, 3, 1] House 0 (2) / \ Rob (2) Skip (0) | | House 2 (9) House 1 (7) / \ / \ Rob (11) Skip (2) Rob (7) Skip (0) | | | | House 4(1) House 3(3) House 3(3) House 2(9) ... ... ... ... ``` A brute-force approach tries every combination — **O(2^n)**. ### Applying the 5-Step Framework **Step 1: Define the state** `dp[i]` = the maximum money we can rob from houses `0` through `i`. **Step 2: Recurrence relation** At house `i`, we have two choices: - **Rob house `i`**: Take `nums[i]` + best we could do up to house `i - 2` (skip adjacent) - **Skip house `i`**: Best we could do up to house `i - 1` ``` dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) ``` This single line captures the entire decision. Either we skip (take `dp[i - 1]`) or we rob (take `dp[i - 2] + nums[i]`). **Step 3: Base cases** - `dp[0] = nums[0]` — only one house, rob it - `dp[1] = max(nums[0], nums[1])` — two houses, rob the richer one **Step 4: Iteration order** Left to right: `i = 2, 3, ..., n - 1` **Step 5: Space optimization** Only depends on `dp[i - 1]` and `dp[i - 2]` → O(1) space. ### Memoization Solution (Top-Down) ```typescript function robMemo(nums: number[]): number { const memo = new Map(); function dp(i: number): number { if (i < 0) return 0; if (memo.has(i)) return memo.get(i)!; const result = Math.max(dp(i - 1), dp(i - 2) + nums[i]); memo.set(i, result); return result; } return dp(nums.length - 1); } ``` ### Tabulation Solution (Bottom-Up) ```typescript function robTab(nums: number[]): number { const n = nums.length; if (n === 0) return 0; if (n === 1) return nums[0]; const dp: number[] = new Array(n); dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (let i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[n - 1]; } ``` ### Space-Optimized Solution ```typescript function rob(nums: number[]): number { if (nums.length === 0) return 0; if (nums.length === 1) return nums[0]; let prev2 = nums[0]; let prev1 = Math.max(nums[0], nums[1]); for (let i = 2; i < nums.length; i++) { const current = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = current; } return prev1; } ``` **Time**: O(n). **Space**: O(1). ### Trace: nums = [2, 7, 9, 3, 1] ``` dp[0] = 2 dp[1] = max(2, 7) = 7 dp[2] = max(dp[1], dp[0] + 9) = max(7, 2 + 9) = 11 dp[3] = max(dp[2], dp[1] + 3) = max(11, 7 + 3) = 11 dp[4] = max(dp[3], dp[2] + 1) = max(11, 11 + 1) = 12 Answer: 12 (rob houses 0, 2, 4: 2 + 9 + 1 = 12) ``` > **Key Pattern**: Whenever you see “can't pick adjacent elements,” think `dp[i] = max(dp[i-1], dp[i-2] + value[i])`. This pattern appears in many variations. --- ## Beginner Problem 4: Maximum Subarray — Kadane's Algorithm (LeetCode 53) You might not think of this as a DP problem, but it absolutely is. It's one of the simplest 1D DP problems, and it introduces an important idea: sometimes `dp[i]` doesn't mean “the answer for the whole array up to i” but rather “the answer **ending at** i.” ### The Problem > Given an integer array `nums`, find the **subarray** with the largest sum and return its sum. A subarray is a **contiguous** non-empty sequence. ### Applying the 5-Step Framework **Step 1: Define the state** `dp[i]` = the maximum subarray sum **ending at index `i`**. This is the clever part. We're not asking “what's the best subarray in the first `i` elements?” — we're asking “what's the best subarray that **must include** element `i` as its last element?” **Step 2: Recurrence relation** At index `i`, we have two choices: - **Extend** the previous subarray: `dp[i - 1] + nums[i]` - **Start fresh** at index `i`: `nums[i]` ``` dp[i] = max(dp[i - 1] + nums[i], nums[i]) ``` In other words: if the previous best subarray ending at `i - 1` is positive, extend it. If it's negative, it would only drag us down, so start fresh. **Step 3: Base case** `dp[0] = nums[0]` — the only subarray ending at index 0 is `[nums[0]]`. **Step 4: Iteration order** Left to right. **Step 5: Space optimization** Only depends on `dp[i - 1]` → single variable. ### Full Solution ```typescript function maxSubArray(nums: number[]): number { let currentMax = nums[0]; let globalMax = nums[0]; for (let i = 1; i < nums.length; i++) { currentMax = Math.max(currentMax + nums[i], nums[i]); globalMax = Math.max(globalMax, currentMax); } return globalMax; } ``` **Time**: O(n). **Space**: O(1). ### Trace: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] ``` i=0: currentMax = -2, globalMax = -2 i=1: currentMax = max(-2 + 1, 1) = 1, globalMax = max(-2, 1) = 1 i=2: currentMax = max(1 + -3, -3) = -2, globalMax = max(1, -2) = 1 i=3: currentMax = max(-2 + 4, 4) = 4, globalMax = max(1, 4) = 4 i=4: currentMax = max(4 + -1, -1) = 3, globalMax = max(4, 3) = 4 i=5: currentMax = max(3 + 2, 2) = 5, globalMax = max(4, 5) = 5 i=6: currentMax = max(5 + 1, 1) = 6, globalMax = max(5, 6) = 6 i=7: currentMax = max(6 + -5, -5) = 1, globalMax = max(6, 1) = 6 i=8: currentMax = max(1 + 4, 4) = 5, globalMax = max(6, 5) = 6 Answer: 6 (subarray [4, -1, 2, 1]) ``` > **Key Insight**: The “ending at index i” state definition is a powerful trick. When you can't figure out how to define `dp[i]` as “the best answer for the first `i` elements,” try defining it as “the best answer **ending at** `i`.” Your final answer is then `max(dp[0], dp[1], ..., dp[n-1])`. --- ## Beginner Problem 5: Coin Change (LeetCode 322) This is the first problem where the transition isn't just “look at the previous one or two elements.” Here, you have **multiple choices** at each step — one for each coin denomination. This is where DP starts to feel distinct from simple Fibonacci-style problems. ### The Problem > Given an array `coins` of coin denominations and a target `amount`, return the **fewest number of coins** needed to make that amount. If it's impossible, return `-1`. You have **infinite** coins of each denomination. ### Applying the 5-Step Framework **Step 1: Define the state** `dp[i]` = the minimum number of coins needed to make amount `i`. **Step 2: Recurrence relation** For each amount `i`, try every coin. If `coin <= i`, we could have arrived at amount `i` by adding that coin to amount `i - coin`: ``` dp[i] = min(dp[i - coin] + 1) for each coin where coin <= i ``` The `+ 1` is because we're using one coin to go from `i - coin` to `i`. **Step 3: Base case** `dp[0] = 0` — zero coins are needed to make amount 0. For all other amounts, initialize to `Infinity` (impossible until proven otherwise). **Step 4: Iteration order** Left to right: `i = 1, 2, 3, ..., amount`. **Step 5: Space optimization** We need access to potentially many previous states (any `dp[i - coin]`), so we keep the full array. **O(amount)** space is already optimal for this problem. ### Tabulation Solution ```typescript function coinChange(coins: number[], amount: number): number { const dp: number[] = new Array(amount + 1).fill(Infinity); dp[0] = 0; for (let i = 1; i <= amount; i++) { for (const coin of coins) { if (coin <= i && dp[i - coin] !== Infinity) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] === Infinity ? -1 : dp[amount]; } ``` **Time**: O(amount × coins.length). **Space**: O(amount). ### Memoization Solution ```typescript function coinChangeMemo(coins: number[], amount: number): number { const memo = new Map(); function dp(remaining: number): number { if (remaining === 0) return 0; if (remaining < 0) return Infinity; if (memo.has(remaining)) return memo.get(remaining)!; let minCoins = Infinity; for (const coin of coins) { const result = dp(remaining - coin); minCoins = Math.min(minCoins, result + 1); } memo.set(remaining, minCoins); return minCoins; } const result = dp(amount); return result === Infinity ? -1 : result; } ``` ### Full Table Walkthrough: coins = [1, 3, 4], amount = 6 ``` Initialize: dp = [0, ∞, ∞, ∞, ∞, ∞, ∞] i=1: Try coin 1: dp[1-1] + 1 = dp[0] + 1 = 1 Try coin 3: 3 > 1, skip Try coin 4: 4 > 1, skip dp[1] = 1 dp = [0, 1, ∞, ∞, ∞, ∞, ∞] i=2: Try coin 1: dp[2-1] + 1 = dp[1] + 1 = 2 Try coin 3: 3 > 2, skip Try coin 4: 4 > 2, skip dp[2] = 2 dp = [0, 1, 2, ∞, ∞, ∞, ∞] i=3: Try coin 1: dp[3-1] + 1 = dp[2] + 1 = 3 Try coin 3: dp[3-3] + 1 = dp[0] + 1 = 1 ← better! Try coin 4: 4 > 3, skip dp[3] = 1 dp = [0, 1, 2, 1, ∞, ∞, ∞] i=4: Try coin 1: dp[4-1] + 1 = dp[3] + 1 = 2 Try coin 3: dp[4-3] + 1 = dp[1] + 1 = 2 Try coin 4: dp[4-4] + 1 = dp[0] + 1 = 1 ← better! dp[4] = 1 dp = [0, 1, 2, 1, 1, ∞, ∞] i=5: Try coin 1: dp[5-1] + 1 = dp[4] + 1 = 2 Try coin 3: dp[5-3] + 1 = dp[2] + 1 = 3 Try coin 4: dp[5-4] + 1 = dp[1] + 1 = 2 dp[5] = 2 dp = [0, 1, 2, 1, 1, 2, ∞] i=6: Try coin 1: dp[6-1] + 1 = dp[5] + 1 = 3 Try coin 3: dp[6-3] + 1 = dp[3] + 1 = 2 ← better! Try coin 4: dp[6-4] + 1 = dp[2] + 1 = 3 dp[6] = 2 dp = [0, 1, 2, 1, 1, 2, 2] Answer: 2 (use coins 3 + 3, or 4 + 1 + 1... wait, 3+3 = 6 ✓ with 2 coins) ``` > **Key Pattern**: When you have multiple choices at each step (different coins, different actions), the transition loops over all choices and takes the best one. This “try all options, take the min/max” pattern is core to DP. --- ## Beginner Problem 6: Unique Paths (LeetCode 62) Time to step into **2D DP**. This problem introduces the idea that sometimes your state needs more than one dimension. ### The Problem > A robot is in the top-left corner of an `m × n` grid. It can only move **right** or **down**. How many unique paths can it take to reach the bottom-right corner? ### Visualizing the Grid ``` Start → ┌───┬───┬───┬───┬───┬───┬───┐ │ R │ → │ → │ → │ → │ → │ → │ ├───┼───┼───┼───┼───┼───┼───┤ │ ↓ │ │ │ │ │ │ │ ├───┼───┼───┼───┼───┼───┼───┤ │ ↓ │ │ │ │ │ │ ★ │ ← Goal └───┴───┴───┴───┴───┴───┴───┘ (m=3, n=7) ``` ### Applying the 5-Step Framework **Step 1: Define the state** `dp[i][j]` = the number of unique paths to reach cell `(i, j)`. This is our first **2D** state. The position in the grid requires two coordinates. **Step 2: Recurrence relation** To reach `(i, j)`, the robot came from either: - Above: `(i - 1, j)` → moved down - Left: `(i, j - 1)` → moved right ``` dp[i][j] = dp[i - 1][j] + dp[i][j - 1] ``` **Step 3: Base cases** - First row: `dp[0][j] = 1` for all `j` — only one way (keep going right) - First column: `dp[i][0] = 1` for all `i` — only one way (keep going down) **Step 4: Iteration order** Top to bottom, left to right (so both `dp[i-1][j]` and `dp[i][j-1]` are already computed). **Step 5: Space optimization** Each row only depends on the row directly above it → can reduce from 2D to 1D. ### 2D Tabulation Solution ```typescript function uniquePaths(m: number, n: number): number { const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(0) ); for (let i = 0; i < m; i++) dp[i][0] = 1; for (let j = 0; j < n; j++) dp[0][j] = 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]; } ``` **Time**: O(m × n). **Space**: O(m × n). ### Full Table Walkthrough: m = 3, n = 4 ``` Initialize base cases: col 0 col 1 col 2 col 3 row 0: 1 1 1 1 row 1: 1 row 2: 1 Fill in row by row: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4 dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3 dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6 dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10 Final table: col 0 col 1 col 2 col 3 row 0: 1 1 1 1 row 1: 1 2 3 4 row 2: 1 3 6 10 ← answer Answer: 10 ``` ### Space-Optimized: 2D → 1D Since each row only depends on the row above, we can use a single 1D array and update it in place: ```typescript function uniquePathsOptimized(m: number, n: number): number { const dp: number[] = new Array(n).fill(1); for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; } ``` How does this work? Before we update `dp[j]`, it still holds the value from the **previous row** (that's `dp[i-1][j]`, the cell above). `dp[j-1]` was already updated in this iteration, so it holds the value from the **current row** (that's `dp[i][j-1]`, the cell to the left). Adding them gives us exactly `dp[i-1][j] + dp[i][j-1]`. **Time**: O(m × n). **Space**: O(n). > **Key Insight**: 2D DP problems often have space optimizations that reduce the table to a single row (or column). The trick is realizing that you only need the **previous row** to compute the current row, and you can overwrite in place if you iterate in the right direction. --- ## 1D vs 2D DP Knowing whether you need a 1D or 2D table comes down to how many dimensions your **state** has. ### 1D DP: Single Variable State The state is described by **one** variable (usually an index or an amount). | Pattern | State definition | Example problems | |---------|-----------------|------------------| | **Linear sequence** | `dp[i]` = answer at position `i` | Climbing Stairs, House Robber, Maximum Subarray | | **Target amount** | `dp[i]` = answer for amount `i` | Coin Change, Perfect Squares | ``` dp: [base][ ][ ][ ][ ][ ][ answer ] ───────────────────────────────────→ i ``` ### 2D DP: Two-Variable State The state needs **two** variables (grid positions, two indices, etc.). | Pattern | State definition | Example problems | |---------|-----------------|------------------| | **Grid traversal** | `dp[i][j]` = answer at cell `(i, j)` | Unique Paths, Minimum Path Sum | | **Two sequences** | `dp[i][j]` = answer for first `i` of seq1 and first `j` of seq2 | Longest Common Subsequence, Edit Distance | | **Interval** | `dp[i][j]` = answer for substring/subarray from `i` to `j` | Palindrome Substrings, Matrix Chain | ``` j → ┌──────────────┐ i │ base cases │ ↓ │ ↘ │ │ ↘ │ │ answer │ └──────────────┘ ``` ### How to Identify Ask yourself: **what information do I need to describe a subproblem?** - “What's the answer for the first `i` elements?” → 1D: `dp[i]` - “What's the answer for amount `a`?” → 1D: `dp[a]` - “What's the answer at position `(row, col)`?” → 2D: `dp[row][col]` - “What's the answer matching first `i` of string A to first `j` of string B?” → 2D: `dp[i][j]` If one variable is enough to fully describe the subproblem, use 1D. If you need two, use 2D. --- ## Space Optimization Techniques One of the most satisfying parts of DP is squeezing out unnecessary space. Here are the most common techniques. ### Technique 1: Two Variables (Rolling Variables) When `dp[i]` depends only on `dp[i - 1]` and `dp[i - 2]`, replace the array with two variables. **Before**: O(n) space ```typescript const dp: number[] = new Array(n + 1); dp[0] = base0; dp[1] = base1; for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; ``` **After**: O(1) space ```typescript let prev2 = base0; let prev1 = base1; for (let i = 2; i <= n; i++) { const current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; ``` **Applies to**: Fibonacci, Climbing Stairs, House Robber, Min Cost Climbing Stairs. ### Technique 2: Single Previous Row (Rolling Array) When a 2D `dp[i][j]` only depends on row `i - 1` and the current row `i`, keep only one row. **Before**: O(m × n) space ```typescript const dp: number[][] = /* 2D array */; 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]; ``` **After**: O(n) space ```typescript const dp: number[] = new Array(n).fill(1); for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; ``` The key insight: when iterating left to right, `dp[j]` (before update) still holds the value from the previous row. This is the “above” cell. `dp[j - 1]` (already updated) holds the value from the current row. This is the “left” cell. **Applies to**: Unique Paths, Minimum Path Sum, Longest Common Subsequence, and most grid DP problems. ### Technique 3: Single Variable When `dp[i]` depends only on `dp[i - 1]`, you need just one variable. ```typescript let prev = baseCase; for (let i = 1; i <= n; i++) { prev = transform(prev); } return prev; ``` ### The Golden Rule > **Always get the correct solution with the full table first.** Then and only then, look at the dependency pattern and optimize. Premature space optimization leads to bugs that are incredibly hard to track down. --- ## Common Pitfalls Even after learning the framework, beginners hit the same mistakes repeatedly. Here's how to avoid them. ### Pitfall 1: Skipping the Framework The biggest mistake is jumping straight to code without defining your state and recurrence. You sit down, stare at the problem, and start typing loops and arrays without knowing what `dp[i]` even represents. **Fix**: Always write down in a comment or on paper: 1. What does `dp[i]` mean? (plain English) 2. What is the recurrence? (formula) 3. What are the base cases? (initial values) ### Pitfall 2: Wrong State Definition If `dp[i]` means the wrong thing, your recurrence will be wrong, your base cases will be wrong, and your answer will be wrong. Everything flows from the state definition. **Example**: For Maximum Subarray, defining `dp[i]` as “the maximum subarray sum in the first `i` elements” makes the recurrence very hard to write. Defining it as “the maximum subarray sum **ending at** `i`” makes it trivial. **Fix**: If the recurrence isn't coming together, reconsider your state definition. Try adding “ending at i” or “starting at i” or an extra dimension. ### Pitfall 3: Wrong Base Cases Off-by-one errors in base cases are extremely common. Is `dp[0]` the answer for zero items or for one item? Does your indexing start at 0 or 1? **Fix**: Trace through the smallest possible inputs by hand. For `n = 0`, `n = 1`, `n = 2` — what should the answer be? Make sure your base cases produce those answers. ### Pitfall 4: Wrong Iteration Order (Bottom-Up) If `dp[i]` depends on `dp[i + 1]` but you iterate left to right, you're reading values that haven't been computed yet. This is a silent bug — the code runs without errors but produces wrong answers. **Fix**: Draw the dependency arrows. Make sure every cell you read has already been filled in by the time you read it. ### Pitfall 5: Premature Space Optimization You try to optimize space before you even have a correct solution. Now you have two problems: the logic is wrong AND the space optimization introduces another source of bugs. **Fix**: Always write the full table solution first. Test it. Verify it's correct. Then and only then, optimize space. ### Pitfall 6: Confusing DP with Greedy You see a problem that asks for the minimum/maximum of something and think, “I'll just always pick the locally best option.” Sometimes that works (greedy). Often it doesn't, and you need DP. **Example**: For Coin Change with coins `[1, 3, 4]` and amount `6`: - **Greedy** (always pick the largest coin): 4 + 1 + 1 = **3 coins** - **DP** (explore all options): 3 + 3 = **2 coins** ✓ **Fix**: If the greedy choice can be proven optimal (greedy choice property), use greedy. If you're not sure, use DP — it explores all options and is always correct. --- ## DP vs Greedy This distinction trips up a lot of people, so let's address it directly. | Aspect | Dynamic Programming | Greedy | |---|---|---| | **Approach** | Try **all** options, pick the best | Make the **locally optimal** choice at each step | | **Guarantee** | Always finds the **global optimum** | Only finds the global optimum **if** greedy choice property holds | | **Time** | Usually O(n²) or O(n × m) | Usually O(n) or O(n log n) | | **When to use** | Need to explore all possibilities | Local optimal = global optimal (provable) | | **Examples** | Coin Change, House Robber, LCS | Activity Selection, Fractional Knapsack, Huffman | ### The Quick Test Ask yourself: **“If I always make the locally best choice, will I always get the globally best answer?”** - If **yes** (and you can prove it) → Greedy - If **no** or **not sure** → DP For Coin Change with standard denominations (1, 5, 10, 25), greedy works — always pick the largest coin. But with arbitrary denominations (1, 3, 4), greedy fails. When in doubt, DP is the safe choice. > **Pro tip**: In interviews, if you're not sure whether greedy works, start with DP. You can mention “a greedy approach might work here, but let me use DP to be safe.” This shows you understand the distinction. --- ## Cheat Sheet ### The 5-Step Framework ``` 1. DEFINE THE STATE → What does dp[i] represent? 2. RECURRENCE RELATION → How does dp[i] relate to smaller subproblems? 3. BASE CASES → What are the initial values? 4. ITERATION ORDER → Which direction do we fill the table? 5. SPACE OPTIMIZATION → Can we reduce the table? ``` ### Common DP Patterns | Pattern | State | Recurrence | Examples | |---------|-------|------------|----------| | **Fibonacci-style** | `dp[i]` = answer at `i` | `dp[i] = dp[i-1] + dp[i-2]` | Climbing Stairs, Fibonacci | | **Decision at each step** | `dp[i]` = best up to `i` | `dp[i] = max/min(take, skip)` | House Robber, 0/1 Knapsack | | **Ending at i** | `dp[i]` = best ending at `i` | `dp[i] = max(dp[i-1] + val, val)` | Maximum Subarray, Longest Increasing Subseq | | **Target building** | `dp[i]` = answer for target `i` | `dp[i] = best(dp[i - choice])` | Coin Change, Perfect Squares | | **Grid traversal** | `dp[i][j]` = answer at `(i,j)` | `dp[i][j] = f(dp[i-1][j], dp[i][j-1])` | Unique Paths, Min Path Sum | | **Two sequences** | `dp[i][j]` = answer for prefixes | `dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])` | LCS, Edit Distance | ### Problem Recognition Signals ``` "How many ways..." → Counting DP "Minimum/maximum..." → Optimization DP "Is it possible..." → Feasibility DP "Longest/shortest..." → Optimization DP Can't pick adjacent elements → House Robber pattern Grid movement → 2D grid DP Making change / filling target → Target building pattern Matching two strings → Two-sequence DP ``` ### Big O Reference | Problem | Time | Space (full) | Space (optimized) | |---------|------|-------------|-------------------| | Fibonacci | O(n) | O(n) | O(1) | | Climbing Stairs | O(n) | O(n) | O(1) | | House Robber | O(n) | O(n) | O(1) | | Maximum Subarray | O(n) | O(n) | O(1) | | Coin Change | O(amount × coins) | O(amount) | O(amount) | | Unique Paths | O(m × n) | O(m × n) | O(n) | | LCS | O(m × n) | O(m × n) | O(n) | | Edit Distance | O(m × n) | O(m × n) | O(n) | --- ## What's Next? You now have the **foundation** for dynamic programming. You understand the core idea (don't solve the same problem twice), the two strategies (memoization and tabulation), the 5-step framework, and six classic problems. But this is just the beginning. There's a whole world of intermediate and advanced DP waiting: - **Longest Common Subsequence (LCS)** and **Edit Distance** — the two-sequence pattern - **0/1 Knapsack** and **Unbounded Knapsack** — the choice-with-weight pattern - **Longest Increasing Subsequence (LIS)** — patience sorting and binary search optimization - **Matrix Chain Multiplication** — interval DP - **DP on Trees** — combining subtree results - **Bitmask DP** — using bits to represent sets - **Digit DP** — counting numbers with certain properties These are all covered in our **“Dynamic Programming Made Simple”** problem-solving patterns guide. Now that you have the fundamentals, those problems will click much faster than they would have before. The most important thing? **Practice**. DP is a skill, not just knowledge. The more problems you solve, the faster you'll recognize patterns, define states, and write transitions. Start with the problems in this guide, then branch out to the patterns above. You've got this. Dynamic programming isn't magic. It's just remembering. --- > **Remember**: Dynamic programming = recursion + memory. If you've already solved it, don't solve it again. Define your state, write the recurrence, set the base cases, pick your direction, and optimize space. That's the whole playbook.

Dynamic Programming 101: The Ultimate Beginner's Guide