Dynamic programming
Dynamic programming is one sentence: write down the answer to each subproblem the first time you compute it, then reuse it instead of computing it again. This chapter starts from a recursion tree that grows exponentially and shows O(2ⁿ) turning into O(n). You then get a five-step method that works the same way on every DP problem in this course.
Why DP exists: a recursion tree that grows out of control
DP is not a new trick. It is a repair for recursion that repeats the same work.
Start with a small problem. You climb a staircase of n steps, moving 1 or 2 steps at a time. How many different ways are there? Use the method from the introduction chapter: stand on step n and look back. The last move has only two possibilities — it came from step n−1 with a 1-step move, or from step n−2 with a 2-step move. The two cases never overlap and nothing else is possible, so f(n) = f(n−1) + f(n−2), with f(1) = 1 and f(2) = 2.
Three lines of recursion, submit — time limit exceeded. What went wrong? Draw the full call tree for f(5). The player below uses the plain Fibonacci version of the same recurrence (f(0) = 0, f(1) = 1) so the numbers are familiar. Step through it and watch the frames marked "⚠️".
f(3) is computed 2 times, f(2) 3 times, f(1) 5 times. Large parts of the tree are identical to each other. This is the cause of the timeout: the repeated work grows exponentially with n.
The answer for f(5) is built directly from the answers for f(4) and f(3). You never need to know what those routes look like in detail. A subproblem answer can be trusted and reused as it is.
The same question is asked many times and the answer never changes. So compute it once, store it, and look it up afterwards. That single change is what dynamic programming does.
Dynamic programming needs both properties. This is also the exact difference from the previous chapter. Divide and conquer has optimal substructure too: merge sort builds a sorted array from two sorted halves. But its subproblems do not overlap — the two halves are disjoint, so no subproblem is ever solved twice, and storing results would gain nothing. Here the subproblems overlap heavily, and storing each answer is exactly what removes the repeated work.
The name "dynamic programming" was chosen for politics
In the 1950s Richard Bellman worked on multi-stage decision problems at RAND. He later wrote in his autobiography that he picked the name partly because the Secretary of Defense at the time disliked the word "research", so he needed a name nobody in Congress could object to. "Dynamic" sounded active, and "programming" then meant planning, not writing code. So do not try to read meaning into the name. It means recursion plus stored results.
Memoization: store each answer the first time
Two extra lines in the code, and O(2ⁿ) becomes O(n). Watch it happen.
The repair is simple. Before the function computes anything, it checks a table and asks "have I answered this exact question before?" If yes, it returns the stored answer. If not, it computes the answer, writes it into the table, and then returns it. Storing a computed result so it can be reused instead of computed again is called memoization; the table is called a memo, and a recursion written this way is called a memoized search, or top-down DP. It helps exactly when the same subproblem is reached many times. Here is the same f(5) tree, walked again with a memo:
The faded nodes are subtrees that were never built. Once a subproblem has been computed, every later request for it costs one table lookup. There are n+1 distinct subproblems and each is computed once, so the total time is O(n). In code this is the brute-force recursion plus two lines:
functools.cache (Python 3.9+) turns any pure function into a memoized one. Remember that Python limits recursion depth to about 1000 by default. For deep inputs, raise it with sys.setrecursionlimit or switch to a table.How to say this in an interview
"I would write the brute-force recursion first. I see that the subproblems overlap, so I add a memo, which makes it a memoized search and brings the time from O(2ⁿ) down to O(n). If a table is preferable, I can rewrite it bottom-up." That sentence shows the whole derivation, which is worth much more than reciting the optimal solution.
Tabulation: fill the table from the bottom up
EASYWorked example A · LC 70 Climbing Stairs — from recursion to a table, then to two variables
Memoization works top-down: it starts at f(n) and computes whatever the recursion happens to reach. Turn the direction around. f(3) depends on f(2) and f(1); f(4) depends on f(3) and f(2); and so on. So start from the smallest subproblem and compute forward, in an order where every value is ready before it is read, filling an array cell by cell. This is called tabulation, or simply filling the DP table. Here it is, one cell at a time:
Top-down and bottom-up compute the same values. The difference is which states get computed. Top-down only visits the states the recursion actually reaches, so it can skip states that this input never needs. Bottom-up fills every state in the table. Neither one is faster in general. Top-down also uses the call stack, so a long chain of subproblems can overflow it; bottom-up has no such limit.
| Form | Direction | Time | Space | When to choose it |
|---|---|---|---|---|
| Plain recursion | Top-down | O(2ⁿ) | O(n) stack | On paper only, to find the transition |
| Memoized search | Top-down | O(n) | O(n) + stack | Easiest to write when the transition is complex or most states are unreachable |
| Tabulation | Bottom-up | O(n) | O(n) | The default when the dependency order is clear; no stack depth limit |
| Tabulation + rolling array | Bottom-up | O(n) | O(1) | Only when the transition reads a fixed number of recent cells |
Complexity and follow-up questions
There are n states and each transition is one addition, so the time is O(n). The full table is O(n) space; because the transition reads only the last two cells, two variables replace it and the space becomes O(1). Common follow-ups: (1) "what if each move can be 1 to m steps?" — dp[i] sums the previous m cells, so the work per state becomes O(m) and the time becomes O(nm); that is an unbounded knapsack (chapter 08). (2) "what if the result must be taken modulo 10⁹+7?" — apply the modulo at every step to avoid overflow. (3) "what if n = 10¹⁸?" — matrix exponentiation gives O(log n), using the fast power idea from the divide and conquer chapter.
The five steps: one routine for every DP problem
Climbing stairs was the warm-up. This routine is what you actually take away.
Replay what you just did and every step can be standardised. This routine applies to all four DP chapters in this course, and the order matters: do not touch the transition until the state is defined in one clear sentence.
Define the state — say in one plain sentence what dp[i] means
"dp[i] is the number of ways to reach step i." "dp[i] is the largest amount from houses 0 through i." Three checks: can you state the meaning, can you read the answer out of the table, and can you derive a transition from it? This step deserves about half of your thinking time.
Write the transition — split the cases by the last step
Stand at dp[i] and look back. What are the possible last steps, and which subproblem does each one land on? Counting problems add the cases; optimization problems take min or max. The cases must not overlap and must cover everything, or the count is wrong.
Initialize — find the cells you can fill without the transition
dp[0], the first row and column, the empty string. These cells are counted directly, not derived. Spend the extra minute counting them by hand; a wrong base value spreads through the whole table.
Fix the iteration order — every cell the transition reads must already be final
The order is not a convention you pick. Read the transition: it names the cells it depends on, and those cells must already hold their final values. If it reads dp[i−1], i must increase. If it reads dp[i+1], i must decrease. In a grid, reading the cell above and the cell on the left forces top to bottom and left to right. In the knapsack chapter this becomes the main point: the same transition gives different results for ascending and descending order.
Check a small example by hand — 3 to 6 values are enough
Do not submit yet. Fill the table for n = 5 by hand and compare it with a brute-force answer. Almost every DP bug is in the base cases or the iteration order, and a small example exposes both.
Three beginner mistakes, all in the first three steps
(1) A vague state. "dp[i] is the answer" is not a definition. Is it "ending at i" or "within the first i elements"? One word changes the whole transition; LC 53 and LC 198 are exactly this pair. (2) Careless initialization. In LC 63, filling the first row with 1 after an obstacle is already wrong. (3) Copying the operator from another problem. Counting adds, optimization takes min or max, feasibility uses OR. The operator follows what this problem asks, not what the last problem used.
Grid DP: the table becomes two-dimensional
MEDIUMWorked example B · LC 62 Unique Paths — one skeleton, three problems
The problem: in an m×n grid, a robot starts at the top left and may only move right or down. How many paths reach the bottom right? Brute force: enumerate every path with backtracking; a 20×20 grid has about 35 billion of them. The DP: the question asks how many, not which ones, which is the usual signal for DP. Following the five steps: state dp[i][j] is the number of paths from (0, 0) to (i, j); the last step can only come from above or from the left, so dp[i][j] = dp[i−1][j] + dp[i][j−1]; the first row and column are 1; and because the transition reads the cell above and the cell on the left, the loops go top to bottom and left to right.
dp[j] still holds the value from the row above, while dp[j-1] already holds this row's new value. A single += therefore reads both sources.An obstacle cell has dp = 0. After the first row or column hits an obstacle, every cell behind it in that line is 0, so you cannot fill the border with 1 unconditionally. The whole problem tests initialization.
Replace + with min: dp[i][j] = min(above, left) + grid[i][j]. The first row and column become prefix sums. The skeleton does not change at all.
Fill upwards: dp[j] = tri[i][j] + min(dp[j], dp[j+1]). Going from the bottom row up makes the end-of-row special cases disappear.
Grid DP in real products
Content-aware image resizing (seam carving) finds a path of pixels with the lowest total energy and removes it, so a photo gets narrower without distorting the subject. That path is exactly the minimum path sum of LC 64, computed row by row. Swipe typing on a phone keyboard and Viterbi decoding in speech recognition are also best-path DP over a grid of states.
House robber: the choose-or-skip model
MEDIUMWorked example C · LC 198 — the bridge to the knapsack chapter. Try it by hand first.
The problem: a row of houses each hold some cash, and taking two neighboring houses sets off the alarm. Find the largest amount you can take without setting it off. Before reading the solution, click through it yourself and see how unintuitive "best under a constraint" is:
Brute force: each house is taken or skipped, so there are 2ⁿ combinations to check — impossible at n = 100. The DP: for house i there are only two decisions. Take it, which gives dp[i−2] + nums[i], because house i−1 must then be skipped. Or skip it, which gives dp[i−1] unchanged. Keep the larger one:
2
7
9
3
1
Complexity and follow-up questions
There are n states and each transition is one comparison, so the time is O(n). The table is O(n); since only the last two cells are read, the space becomes O(1). Common follow-ups: (1) "what if the houses form a circle?" (LC 213) — the first and last house cannot both be taken, so run the same DP on [0, n−2] and on [1, n−1] and take the larger result. (2) "what if the houses form a tree?" (LC 337) — each node returns two values, one for taken and one for skipped; that is tree DP, chapter 10. (3) "why does the dp[i−1] term not add nums[i]?" — go back to the state definition: "the best over houses 0 through i" does not promise that house i is taken.
Where greedy fails: coin change
MEDIUMWorked example D · LC 322 — the greedy method from the previous chapter breaks here
The problem: given coin values (unlimited coins of each value) and a target amount, find the fewest coins that add up to it, or −1 if it cannot be done. The everyday instinct, which is also the greedy method from the previous chapter, is always take the largest coin that still fits. That works for real euro and dollar coins. Now try the values [1, 3, 4] with a target of 6:
Take 4 (2 left) → 3 does not fit, take 1 (1 left) → take 1 again. 3 coins. Every single step was locally best, and after the first one the path through two 3s can never be reached again.
dp[6] tries all three possible last coins, 1, 3, and 4, and keeps the minimum. 2 coins. It does not commit to a choice; it computes the consequence of every choice.
Why does greedy fail here? The coin set [1, 3, 4] does not have the greedy choice property: taking 4, the locally best move, destroys the structure of the globally best answer, 3 + 3. The greedy chapter stated the rule: if you cannot prove the exchange argument, do not use greedy. Fall back to DP. State: dp[a] is the fewest coins that add up to exactly a, or infinity if a cannot be formed. Split the cases by which coin was the last one:
float("inf") plus 1 is still inf, so there is no overflow. An amount that cannot be formed keeps its infinity value all the way to the end.Preview: this problem has a second identity
"Unlimited coins of each value, reach a target amount" is the standard shape of an unbounded knapsack. Chapter 08 models LC 322 again from that angle: why can the inner and outer loops be swapped there? And why does replacing min with a count turn it into LC 518? Modeling the same problem twice is deliberate.
Checkpoint: three strategies compared
You have now seen three strategies applied to the same kind of problem. Backtracking enumerates every combination: always correct, but with k coin values and a target amount the search tree is about O(k^amount). Greedy takes the largest coin each time: fastest, but it needs a proof, and it fails outright on [1, 3, 4]. DP enumerates the decisions and stores the subproblem answers: always correct, in polynomial time. Working through an optimization problem in that order is a good way to answer in an interview.
Problem set: 13 DP problems to start with
Core setGrouped as linear, grid, and decision problems, from easier to harder. Think for 30 seconds before opening the hint.
Chapter quiz
✎ QuizAnswer all 8 correctly to mark this chapter as complete.
Which two properties must a problem have before dynamic programming helps?
What is the most accurate description of how memoized recursion relates to filling a table?
Climbing stairs, 1 or 2 steps at a time: how many ways are there to climb 5 steps? (Fill the table by hand: dp[1] = 1, dp[2] = 2, …)
In LC 62 Unique Paths (the robot moves only right or down), which transition is correct?
In House Robber, dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Why does the first term not add nums[i]?
Which of these show that a state definition is good enough? (Choose all that apply)
Coins 1, 3, 4 and a target of 6. Taking the largest coin first gives 4+1+1 = 3 coins, but the answer is 3+3 = 2 coins. What does this show?
The climbing stairs transition dp[i] = dp[i-1] + dp[i-2] reads only the last two cells. If you replace the whole dp array with two rolling variables, what is the space complexity?
- DP is recursion plus stored results. It applies when the problem has overlapping subproblems (storing pays off) and optimal substructure (stored answers combine into the answer above). Divide and conquer has the second but not the first.
- The standard path: brute-force recursion → memoized search → tabulation → rolling array. Being able to walk through that chain is worth more in an interview than reciting the final solution.
- The five steps: define the state → split by the last step → set the base cases → fix the iteration order → check a small example by hand. Do not touch the transition before the state is clear.
- The operator follows the question: counting problems add (LC 70, LC 62), optimization problems take min or max (LC 64, LC 198, LC 322). Reuse the skeleton, never the operator.
- Choose or skip (LC 198) is the most important decision model in DP and leads straight into knapsack. Enumerate the last step (the last coin in LC 322) is the general way to start writing a transition.
- The iteration order comes from the transition, not from habit. Every cell the transition reads must already hold its final value.
- Complexity of a table DP is (number of states) × (work per transition), and the table itself counts in the space. Space drops to O(k) only when the transition reads a fixed set of k recent cells — LC 322 does not qualify. Write the full table correctly first, then optimize.