# Dynamic Programming: A Gentle Intro > Dynamic programming taught from intuition: overlapping subproblems and memoization on naive Fibonacci, bottom-up tabulation with climbing stairs, then coin change as real DP and how to recognize an optimal-substructure problem when you see one. --- # Dynamic Programming: A Gentle Intro Dynamic programming has a scary name and a simple idea: if solving a problem means solving the same smaller problems over and over, solve each one once and write the answer down. That is the whole trick. Everything else is figuring out what the "smaller problems" are. Most people meet DP as a wall of clever-looking code and bounce off it. We are going to do the opposite: start from a plain recursive function you already understand, watch it recompute the same thing a million times, and fix it with one small change. By the end you will recognize the pattern and know when to reach for it. Every example runs in Python right in the page - change the numbers and see what happens. ## How to read this Read in order. Memoization (phase 1) is the "aha," tabulation (phase 2) is the same idea turned inside out, and coin change (phase 3) is where DP earns its keep on a problem a greedy loop gets wrong. ## The phases 1. **[Overlapping Subproblems and Memoization](01-overlapping-subproblems-and-memoization.md)** 🟢 Basic - naive recursive Fibonacci is exponentially slow because it recomputes the same subproblems; one memo makes it instant. 2. **[Bottom-Up Tabulation](02-bottom-up-tabulation.md)** 🟡 Intermediate - build the answer from the smallest cases upward with a loop and a table, using the climbing-stairs problem. 3. **[Coin Change and Spotting DP](03-coin-change-and-spotting-dp.md)** 🟡 Intermediate - the classic min-coins problem where greedy fails, plus the two signals that tell you a problem is dynamic programming. --- # Overlapping Subproblems and Memoization The fastest way to feel why dynamic programming exists is to write a function that is correct but painfully slow, watch exactly where it wastes its time, then fix it with a few lines. Fibonacci is the classic case: short enough to hold in your head, slow enough to make the point. ## The naive version, and why it crawls Each Fibonacci number is the sum of the two before it: `fib(n) = fib(n-1) + fib(n-2)`, with `fib(0) = 0` and `fib(1) = 1`. That definition is also a working program. ```python runnable calls = 0 def fib(n): global calls calls += 1 if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(30), "computed in", calls, "calls") ``` ```console 832040 computed in 2692537 calls ``` *What just happened:* computing `fib(30)` took over 2.6 million function calls to produce one number. The reason is that `fib(30)` calls `fib(29)` and `fib(28)`, but `fib(29)` also calls `fib(28)`, and both of those call `fib(27)`, and so on. The same subproblems get solved again and again down separate branches of the call tree. That repeated work is called **overlapping subproblems**, and it makes the running time grow like `O(2^n)` - roughly double for every step up. 📝 **Terminology.** *Overlapping subproblems* means the recursive calls keep asking the same questions. If each subproblem were unique (like the two halves in merge sort), there would be nothing to cache and DP would not help. Overlap is the thing dynamic programming exploits. ## The fix: remember what you already computed The wasted work is entirely re-computation. `fib(28)` has one answer; there is no reason to derive it more than once. So keep a dictionary - a **memo** - mapping each `n` to its answer. Before computing `fib(n)`, check the memo. Compute it only on a miss, and store the result on the way out. ```python runnable calls = 0 def fib(n, memo=None): global calls calls += 1 if memo is None: memo = {} if n < 2: return n if n in memo: return memo[n] memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n] print(fib(30), "computed in", calls, "calls") ``` ```console 832040 computed in 59 calls ``` *What just happened:* same answer, but 59 calls instead of 2.6 million. Each distinct subproblem `fib(2)` through `fib(30)` is computed exactly once and cached; every other request is an instant memo hit. This top-down style - ordinary recursion plus a cache - is called **memoization**. The running time drops from `O(2^n)` to `O(n)`, because there are only `n` distinct subproblems and each costs constant work once its inputs are known. 💡 **Key point.** Memoization does not change *what* the function computes - only how many times it computes each piece. You keep the readable recursive definition and bolt a cache onto it. ⚠️ **Gotcha: the mutable default argument.** Do not write `def fib(n, memo={})`. In Python a default argument is created once and shared across every call, so the memo would persist between unrelated top-level calls and quietly leak state. The `memo=None` then `if memo is None: memo = {}` pattern gives each fresh call its own memo. (Python's own `functools.lru_cache` decorator sidesteps this entirely and is what you would use in real code.) ## The same memoized Fibonacci, in other languages The shape is identical everywhere: a base case, a cache lookup, compute-and-store on a miss. Only the cache type and the syntax change. Flip through the tabs. [[codegroup Memoized Fibonacci]] ```python def fib(n, memo=None): if memo is None: memo = {} if n < 2: return n if n in memo: return memo[n] memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n] ``` ```javascript function fib(n, memo = {}) { if (n < 2) return n; if (n in memo) return memo[n]; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; } ``` ```typescript function fib(n: number, memo: Record = {}): number { if (n < 2) return n; if (n in memo) return memo[n]; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; } ``` ```java static long fib(int n, Map memo) { if (n < 2) return n; if (memo.containsKey(n)) return memo.get(n); long result = fib(n - 1, memo) + fib(n - 2, memo); memo.put(n, result); return result; } ``` ```cpp long long fib(int n, std::unordered_map& memo) { if (n < 2) return n; if (memo.count(n)) return memo[n]; long long result = fib(n - 1, memo) + fib(n - 2, memo); memo[n] = result; return result; } ``` ```go func fib(n int, memo map[int]int) int { if n < 2 { return n } if v, ok := memo[n]; ok { return v } memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] } ``` ```rust use std::collections::HashMap; fn fib(n: u64, memo: &mut HashMap) -> u64 { if n < 2 { return n; } if let Some(&v) = memo.get(&n) { return v; } let result = fib(n - 1, memo) + fib(n - 2, memo); memo.insert(n, result); result } ``` [[/codegroup]] The typed languages pass the memo in by reference (`&`, `&mut`, or a shared object) so that every branch of the recursion writes into the *same* cache - exactly what makes the caching work. Pass a copy per call and you are back to the slow version. ## Check yourself ```quiz [ { "q": "What makes naive recursive Fibonacci exponentially slow?", "choices": ["It uses too much memory per call", "The same subproblems like fib(28) get recomputed on many separate branches", "Recursion is always slower than a loop", "Python function calls are unusually slow"], "answer": 1, "explain": "fib(30) and fib(29) both need fib(28), and so on down the tree - the same subproblems are solved again and again, doubling the work at each level." }, { "q": "What does memoization store, and keyed by what?", "choices": ["The entire call stack", "The final answer only", "The answer to each subproblem the first time it is computed, keyed by that subproblem's inputs", "A log of every function ever called"], "answer": 2, "explain": "A memo maps a subproblem's inputs to its answer, so the second request for the same inputs is an instant lookup instead of a recomputation." }, { "q": "Memoized Fibonacci turns the running time from O(2^n) into roughly what?", "choices": ["O(1)", "O(log n)", "O(n)", "O(n^2)"], "answer": 2, "explain": "There are only n distinct subproblems; each is computed once and every other request is a cache hit, so total work is proportional to n." } ] ``` --- # Bottom-Up Tabulation Memoization works top-down: you ask for the big answer and let recursion fill the cache as it goes. **Tabulation** turns that around. You start from the smallest subproblems, solve them first, and build upward until you reach the one you actually wanted. Same subproblems, same answers - opposite direction. ## A new problem: climbing stairs You are climbing a staircase with `n` steps. Each move takes you up either 1 step or 2 steps. How many distinct ways are there to reach the top? Think about your *last* move. To land on step `n`, you either came from step `n-1` (a 1-step move) or from step `n-2` (a 2-step move). Those two groups never overlap, so the total is their sum: ``` ways(n) = ways(n-1) + ways(n-2) ways(0) = 1 (one way to "stand at the bottom": do nothing) ways(1) = 1 (a single 1-step move) ``` That is the same recurrence as Fibonacci. The lesson underneath: a huge share of DP is spotting that "the answer for `n` is built from the answers for smaller inputs," then writing that relationship down. ## Filling the table Instead of recursing, make an array `dp` where `dp[i]` holds the number of ways to reach step `i`. Seed the smallest cases, then let a loop fill each cell from the two below it. ```python runnable def climb_stairs(n): if n <= 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] for n in range(1, 8): print(n, "steps ->", climb_stairs(n), "ways") ``` ```console 1 steps -> 1 ways 2 steps -> 2 ways 3 steps -> 3 ways 4 steps -> 5 ways 5 steps -> 8 ways 6 steps -> 13 ways 7 steps -> 21 ways ``` *What just happened:* the loop never recurses and never re-computes. By the time it reaches `dp[i]`, the two cells it needs (`dp[i-1]` and `dp[i-2]`) are already filled, so each cell is a single addition. That is the essence of tabulation: order the subproblems so that every answer is ready before you need it. The running time is `O(n)` with `O(n)` space for the table. 💡 **Key point.** Memoization and tabulation compute exactly the same subproblems. Memoization discovers the order lazily through recursion; tabulation commits to the order up front with a loop. Pick whichever reads more clearly for the problem - tabulation avoids recursion-depth limits, memoization can skip subproblems it never needs. ## Trimming the memory: the rolling version Look at the loop again: to fill `dp[i]` you only ever look at the previous two cells. The rest of the table is dead weight. So keep just two variables and slide them forward. ```python runnable def climb_stairs(n): if n <= 1: return 1 prev, curr = 1, 1 # ways to reach step 0 and step 1 for _ in range(2, n + 1): prev, curr = curr, prev + curr return curr print(climb_stairs(7)) print(climb_stairs(40)) ``` ```console 21 165580141 ``` *What just happened:* `prev` and `curr` always hold the last two results, and each step rolls them forward by one. Same `O(n)` time, but now `O(1)` space - constant memory no matter how big `n` gets. This "keep only what the next step needs" trick is one of the most common DP optimizations. ⚠️ **Gotcha.** The two-variable update relies on doing both assignments at once. In Python, `prev, curr = curr, prev + curr` evaluates the whole right side first, so `prev + curr` still uses the old `prev`. Writing it as two separate lines (`prev = curr` then `curr = prev + curr`) overwrites `prev` too early and silently computes the wrong sequence. ## Check yourself ```quiz [ { "q": "What is the core difference between tabulation and memoization?", "choices": ["Tabulation builds answers bottom-up in a table with a loop; memoization is top-down recursion that caches results", "They are two different names for the same code", "Tabulation always uses recursion; memoization always uses loops", "Tabulation only works for Fibonacci-shaped problems"], "answer": 0, "explain": "Both solve the same subproblems. Tabulation orders them smallest-first and fills a table iteratively; memoization recurses top-down and caches each result on first computation." }, { "q": "For climbing stairs with 1- or 2-step moves, why is ways(n) = ways(n-1) + ways(n-2)?", "choices": ["Because the answers happen to be Fibonacci numbers", "Because your last move came from either step n-1 or step n-2, and those two sets of paths never overlap", "Because you can only ever take 2-step moves", "It is a coincidence that only holds for small n"], "answer": 1, "explain": "Every path to step n ends with a final move from n-1 or from n-2. Counting each group and adding them (they are disjoint) gives the recurrence." }, { "q": "What does the rolling two-variable version save compared to the full table?", "choices": ["Time - it changes the big-O", "Nothing, it is only a style preference", "Memory - it keeps O(1) space instead of an O(n) table", "Accuracy on large inputs"], "answer": 2, "explain": "Each step needs only the previous two results, so two variables suffice. Time stays O(n); space drops from O(n) to O(1)." } ] ``` --- # Coin Change and Spotting DP Fibonacci and climbing stairs are gentle: there is one number to compute and the recurrence is handed to you. Real DP problems are about finding the *best* option among many, and this is where the technique earns its reputation. Coin change is the classic first real one. ## The problem, and why greedy is not enough Given coin denominations and a target amount, what is the **fewest** coins that add up to the amount? With US-style coins `[1, 5, 10, 25]`, a natural instinct is to be greedy: keep taking the biggest coin that fits. For everyday coins that happens to work - but it is not a general rule, and it is easy to break. Take coins `[1, 3, 4]` and amount `6`. Greedy grabs the `4`, leaving `2`, then two `1`s: that is `4 + 1 + 1`, three coins. But `3 + 3` is two coins. Greedy walked confidently to the wrong answer because a locally biggest choice can force worse choices later. DP fixes this by considering every first coin and trusting the smaller answers. ```python runnable def coin_change(coins, amount): INF = amount + 1 # a stand-in for "impossible", larger than any real answer dp = [0] + [INF] * amount # dp[a] = fewest coins to make amount a for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount] if dp[amount] != INF else -1 print(coin_change([1, 3, 4], 6)) # greedy would say 3; the truth is 2 print(coin_change([1, 5, 10, 25], 63)) print(coin_change([2], 3)) # odd amount, only even coins -> impossible ``` ```console 2 6 -1 ``` *What just happened:* `dp[a]` holds the fewest coins to make amount `a`. To fill it, we try every coin `c` that fits and ask: "what if this coin is the last one I add?" That leaves `a - c` to make, whose best answer is already sitting in `dp[a - c]`, so the candidate is `dp[a - c] + 1`. Take the smallest candidate over all coins. Amounts that can never be formed keep the `INF` sentinel and report `-1`. This runs in `O(amount * number_of_coins)`. 💡 **Key point.** The greedy version commits to one coin and never looks back. DP tries *every* possible last coin and lets the already-solved subproblems decide which one leads to the best total. That willingness to consider all first moves, backed by cached answers, is what makes it correct where greedy is not. ## How to recognize a DP problem You will not always be told "this is dynamic programming." Two properties, present together, are the tell: - **Optimal substructure.** The best answer to the whole problem can be built from the best answers to its subproblems. In coin change, the best way to make `6` is "one more coin than the best way to make `6 - c`" for the right choice of `c`. If the pieces of an optimal solution are themselves optimal, you have it. - **Overlapping subproblems.** The same subproblems come up repeatedly, so caching pays off. If every subproblem were unique, you would just have plain recursion (like merge sort) and DP would add nothing. 📝 **Terminology.** A problem with optimal substructure but *no* overlap is usually a divide-and-conquer problem, not DP. A problem with overlap but no optimal substructure (where a locally best choice can be undone later in a way caching cannot capture) may not be solvable by DP at all. You need both. ⚠️ **Gotcha.** Greedy and DP can agree on some inputs and disagree on others, as the two coin sets above showed. "It worked on my examples" is not proof a greedy shortcut is correct. When the problem asks for an optimum and choices interact, reach for DP unless you can prove greedy is safe for your specific coin system. ## The recipe Once you suspect DP, the steps are always the same: 1. Define the subproblem precisely - what does `dp[i]` (or `dp[i][j]`) *mean*? 2. Write the recurrence - how is `dp[i]` built from smaller entries? 3. Set the base cases - the smallest inputs whose answers you know outright. 4. Choose a direction - top-down memoization or bottom-up tabulation. 5. Read the answer out of the table. Nail step 1 and the rest tends to follow. A vague subproblem definition is the single most common reason a DP attempt stalls. ## Check yourself ```quiz [ { "q": "Why does greedy 'always take the biggest coin' fail for coins [1, 3, 4] and amount 6?", "choices": ["Greedy is never correct for any problem", "Greedy takes 4 + 1 + 1 (three coins), but 3 + 3 (two coins) is better", "6 cannot be made from those coins at all", "Greedy and DP give the same answer here"], "answer": 1, "explain": "Grabbing the biggest coin (4) forces two 1s afterward for three coins total, while 3 + 3 needs only two - a locally biggest choice led to a worse overall result." }, { "q": "In the coin-change table, what does dp[a] represent?", "choices": ["The number of coins whose value equals a", "The fewest coins needed to make amount a", "Whether amount a is even", "The largest coin not exceeding a"], "answer": 1, "explain": "dp[a] is the minimum number of coins that sum to a; the algorithm fills it by trying each coin as the last one added." }, { "q": "Which two properties together signal that a problem is a good fit for dynamic programming?", "choices": ["Recursion and loops", "Sorting and searching", "Optimal substructure and overlapping subproblems", "Large inputs and small outputs"], "answer": 2, "explain": "Optimal substructure means the best whole answer is built from best sub-answers; overlapping subproblems means those sub-answers repeat, so caching them pays off. DP needs both." } ] ```