DP Foundations
You have 6 cents to pay and coins worth 1, 3 and 4. What is the fewest number of coins? The obvious move — take the biggest coin that fits, again and again — gives 4 + 1 + 1, three coins. The right answer is 3 + 3, two coins. To be sure you have the best answer you seem to need to try every combination, and the number of combinations explodes as the amount grows. Yet a computer can answer this for an amount of one million in a fraction of a second. The trick is dynamic programming (DP): solve every smaller amount once, write each answer down, and build the big answer out of the small ones.
This lesson is the first in Module 6 · Dynamic Programming. It gives you one framework — five questions you answer on paper before writing any code — and then applies it to ten classic problems so you can see the same reasoning produce ten different algorithms. Every later DP lesson (1-D DP, knapsack, sequences, strings, grids, intervals, trees, bitmasks, digits, games, probabilities) is this framework with a different kind of state.
You should be comfortable with recursion and proof by induction (Recursion & Mathematical Induction) and with Big-O (Complexity Analysis). Backtracking & Recursion helps: much of DP starts life as a backtracking search that keeps asking the same questions.
Why it exists
A recursive solution splits a problem into smaller problems of the same kind. When the smaller problems are all different — as in merge sort, where the two halves never overlap — plain recursion is efficient. When the smaller problems repeat, plain recursion is a disaster: it re-solves the same question every time it meets it, and the repeats multiply.
Fibonacci numbers are the standard example. The rule is with and . Coding that rule directly, fib(30) makes 2,692,537 function calls to compute a value that depends on only 31 distinct subproblems, through . Each call to fib(n) makes two more calls, and those overlap almost completely.
| Calls made by naive recursion | Distinct subproblems | ||
|---|---|---|---|
| 5 | 5 | 15 | 6 |
| 10 | 55 | 177 | 11 |
| 20 | 6,765 | 21,891 | 21 |
| 30 | 832,040 | 2,692,537 | 31 |
(The call count is exactly , which grows like .) Dynamic programming is the discipline of noticing that the distinct subproblems are few, and arranging to solve each one exactly once.
The name is historical. Richard Bellman developed the method at the RAND Corporation in the early 1950s for multistage decision problems — inventory, scheduling, control. In his autobiography (Eye of the Hurricane, 1984) he explains that "programming" meant planning, as in "linear programming", and that he chose "dynamic" partly because it sounded impressive and was hard to use in a negative sense, which helped shield mathematical research from a Secretary of Defense who disliked the word "research". So "dynamic programming" does not mean writing dynamic code; read it as "multistage planning with a table".
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "number of ways", "how many distinct", "count … modulo " | Counting DP: add up the ways from each smaller state |
| "minimum cost / fewest / maximum value / longest / shortest" and choices at each step | Optimisation DP: min or max over the choices |
| "is it possible", "can you reach / segment / partition" | Feasibility DP: boolean table, or over the choices |
| Your recursive solution's call tree repeats the same arguments | Memoize it — that is already DP |
| Choices made in order (left to right, item by item, day by day) and only a little of the past matters | A state like dp[i] or dp[i][small extra info] |
| Greedy "take the best-looking option" fails on a small example | Probably DP (the greedy counterexample is your proof that you must consider every option) |
| Constraints like with a quadratic answer, or with | Size of the table tells you the state: states, or a bitmask |
| "subsequence" (not "subarray") | Sequence DP over prefixes |
| Input is a set of items, a capacity or a target sum | Knapsack-style dp[i][capacity] |
| Need the actual answer, not just its value | DP plus reconstruction (parent pointers or walking back through the table) |
And the anti-triggers. If every subproblem is different (merge sort, binary search), DP adds nothing. If the problem asks for all solutions and there are exponentially many, DP can count them but cannot list them faster than their number — use backtracking. If a simple exchange argument proves a greedy choice is always safe, greedy is simpler and faster.
Intuition & first principles
A tiny example: climbing stairs
You are at the bottom of a staircase with 5 steps. Each move climbs 1 step or 2 steps. How many different sequences of moves get you to the top?
Think about the last move. You arrived at step 5 either from step 4 (a 1-step) or from step 3 (a 2-step). Those are the only two possibilities, and they never overlap (the last move differs). So:
ways to reach 5 = ways to reach 4 + ways to reach 3
The same holds for every step. Start from the bottom: there is 1 way to "reach" step 0 (do nothing) and 1 way to reach step 1. Then:
| step | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| ways | 1 | 1 | 2 | 3 | 5 | 8 |
Eight ways. You did not list them; you never needed to. You only asked "what was the last move?" and used answers you had already written down. That is all of DP: a big question, rewritten in terms of the same question about smaller inputs, with every answer recorded so it is never recomputed.
Overlapping subproblems
A subproblem is the same question asked about a smaller input — "ways to reach step 3" is a subproblem of "ways to reach step 5". Subproblems overlap when different branches of the recursion ask the same question. In the Fibonacci call tree, fib(3) is requested by fib(5) and by fib(4); fib(2) is requested three times:
graph TD
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3a["fib(3)"]
F4 --> F3b["fib(3)"]
F4 --> F2a["fib(2)"]
F3a --> F2b["fib(2)"]
F3a --> F1a["fib(1)"]
F3b --> F2c["fib(2)"]
F3b --> F1b["fib(1)"]
style F3a fill:#f96
style F3b fill:#f96
style F2a fill:#ff0
style F2b fill:#ff0
style F2c fill:#ff0
Draw each distinct subproblem once, with an arrow to each subproblem it needs, and the tree collapses into a small directed acyclic graph (DAG: arrows that never loop back) — the subproblem graph:
graph LR
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3["fib(3)"]
F4 --> F3
F4 --> F2["fib(2)"]
F3 --> F2
F3 --> F1["fib(1)"]
F2 --> F1
F2 --> F0["fib(0)"]
Six nodes instead of fifteen calls. DP's running time is (number of nodes) × (work per node), which here is instead of . The subproblem graph must be acyclic: if subproblem A needs B and B needs A, there is no order in which to solve them, and you need a different tool (for example shortest paths when the "subproblems" are distances in a graph with cycles).
Optimal substructure
For optimisation problems there is a second requirement. Optimal substructure means: an optimal solution to the big problem is built from optimal solutions to its subproblems. In coin change, the fewest-coins way to pay 6 ends with some coin ; the coins before it pay , and they must themselves be a fewest-coins way to pay . If they weren't, swap in a better way to pay and you would pay 6 with fewer coins — contradicting optimality. This "cut and paste" argument (CLRS §14.3) is how you prove optimal substructure for nearly every DP in this module.
Optimal substructure can fail. The classic example (CLRS §14.3): the longest simple path in a graph (a path that never repeats a vertex). The longest simple path from to through is not in general the longest path from to glued to the longest path from to , because the two pieces may share vertices, and the glued result is no longer simple. The subproblems interfere with each other. Shortest paths do not have this problem, which is why they have polynomial algorithms and longest simple path is NP-hard.
The two properties, in one line each
Overlapping subproblems: the same smaller question comes up many times, so remembering answers pays off. Optimal substructure: the best answer to the big question is assembled from best answers to smaller questions, so remembering only the best answer per subproblem is enough. Counting and feasibility DPs need a cousin of the second property: the answer to the big question is a sum (or an "or") over disjoint cases, each of which is a smaller question.
DP is recursion plus a table — or a shortest path in a DAG
Two equivalent pictures help:
- Recursion with a memory. Write the recursive solution, then make it remember. That is memoization (from "memo", a note to self).
- A walk over the subproblem DAG. Each subproblem is a vertex; the answer at a vertex is computed from the vertices it points to. Solving them in an order where every vertex comes after the ones it needs is a topological order, and an optimisation DP is literally a shortest (or longest) path in that DAG. This view is developed in DAG DP.
The five parts of every DP
Before any code, answer these five questions on paper. They are the whole framework, and every later lesson in this module uses exactly these headings.
- State — what a subproblem is. A short description with parameters: "
dp[a]= the fewest coins that sum to exactlya". The parameters (here justa) become the dimensions of your table. Write it as a full English sentence; a vague state is the root of most DP bugs. - Transition — how a state's answer is computed from smaller states. Usually: "look at the last decision; for each option, combine the option's cost with the answer of the state it leaves you in". For coin change: .
- Base case — the states small enough to answer directly, without the transition. : zero coins pay zero. Base cases also include "impossible" states, which get a sentinel value such as .
- Answer — which state (or which combination of states) answers the original question. Here , converted to if it is still . Sometimes it is a max over all states ("LIS ending anywhere").
- Order — an order of computing states in which every state's inputs are already computed. Here increasing , because only reads smaller amounts. In top-down memoization the recursion finds the order for you.
Then two numbers:
- Time = (number of states) × (work per transition). Coin change: states × options = .
- Space = number of states you must keep at once (often reducible; see Space optimisation).
flowchart TD
Q["Problem statement"] --> CH["List the choices made at each step"]
CH --> ST["1. State: what a subproblem is"]
ST --> TR["2. Transition: answer from smaller states"]
TR --> BC["3. Base case: smallest states, impossible states"]
BC --> AN["4. Answer: which state is the result"]
AN --> OR["5. Order: inputs before outputs"]
OR --> CX["Time = states x transition cost"]
CX --> CODE["Code: memo or table"]
CODE --> CHK["Check against brute force on small inputs"]
CHK -->|"mismatch"| ST
The arrow back from "check" to "state" is not decoration. When a DP gives wrong answers, the state is the usual culprit — it does not capture everything the future depends on. DP Debugging & How to Find the State is a whole lesson on that loop.
Mechanics
Memoization (top-down)
Write the transition as a recursive function. Before computing, look the argument up in a cache; after computing, store the result.
from functools import lru_cache
coins = [1, 3, 4]
@lru_cache(maxsize=None)
def f(a):
if a == 0:
return 0
return 1 + min((f(a - c) for c in coins if c <= a), default=float("inf"))
print(f(6)) # 2
The recursion starts from the question you care about and only visits subproblems it actually needs. That can be a big saving when the state space is sparse (for example, a state is a pair of large numbers but only a few pairs are reachable). The costs are function-call overhead, hash lookups if the cache is a dictionary, and recursion depth: the deepest chain of nested calls equals the longest path in the subproblem DAG, which for coin change with a 1-cent coin is the amount itself.
Trace: memoized fib(5)
Each row is one event in the order it happens. "call" means the function body starts; "hit" means the cache already had the answer; "store" means a value was computed and written to the cache. Base cases store immediately.
| # | Event | Cache after the event |
|---|---|---|
| 1 | call fib(5) | — |
| 2 | call fib(4) | — |
| 3 | call fib(3) | — |
| 4 | call fib(2) | — |
| 5 | call fib(1) → base, 1 | {1: 1} |
| 6 | call fib(0) → base, 0 | {1: 1, 0: 0} |
| 7 | store fib(2) = 1 + 0 = 1 | {…, 2: 1} |
| 8 | hit fib(1) = 1 (asked by fib(3)) | unchanged |
| 9 | store fib(3) = 1 + 1 = 2 | {…, 3: 2} |
| 10 | hit fib(2) = 1 (asked by fib(4)) | unchanged |
| 11 | store fib(4) = 2 + 1 = 3 | {…, 4: 3} |
| 12 | hit fib(3) = 2 (asked by fib(5)) | unchanged |
| 13 | store fib(5) = 3 + 2 = 5 | {…, 5: 5} |
Six "call" events (one per distinct subproblem) and three cache hits, instead of fifteen calls. The recursion first dives straight down the left spine 5 → 4 → 3 → 2 → 1, so the maximum depth is ; every right-hand call is a cache hit.
Tabulation (bottom-up)
Allocate an array indexed by the state, fill the base cases, then loop over states in an order where inputs come before outputs:
INF = float("inf")
coins, amount = [1, 3, 4], 6
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
print(dp[amount]) # 2
No recursion, no hash lookups, memory accessed in order (fast on real caches — see How Data Structures Live in Memory). The price: you must work out the order yourself, and you compute every state, even those the answer never needs.
Trace: coin change, coins = [1, 3, 4], amount = 6
The table, filled left to right. For each amount the "options" column shows for every coin ; the minimum wins. "Last coin" is the first coin (in input order) that achieved the minimum — we keep it for reconstruction.
| options | last coin | ||
|---|---|---|---|
| 0 | base case | 0 | — |
| 1 | c=1: | 1 | 1 |
| 2 | c=1: | 2 | 1 |
| 3 | c=1: 3, c=3: | 1 | 3 |
| 4 | c=1: 2, c=3: 2, c=4: | 1 | 4 |
| 5 | c=1: , c=3: , c=4: | 2 | 1 |
| 6 | c=1: , c=3: , c=4: | 2 | 3 |
The answer is . To find which coins, walk back: at 6 the last coin was 3, leaving 3; at 3 the last coin was 3, leaving 0. Coins: 3 + 3. Greedy (largest coin first) would take 4, then 1, then 1 — three coins — which is why this problem needs DP.
Notice row 5: coin 1 and coin 4 tie at 2. Either is a correct "last coin"; the code below keeps the first one it sees (strict <), so 5 = 1 + 4. Ties are why reconstructed answers can differ between two correct implementations.
Recursion depth: how deep can memoization go?
Every nested call takes a stack frame. When the chain is longer than the stack allows, the program crashes — not with a wrong answer, with an exception or a segmentation fault. The limits differ a lot by language. The numbers below were measured on the machine used to test this lesson (macOS, default settings) with a one-argument recursive function; real DP functions have bigger frames and go less deep.
| Language | Default limit | Measured depth before failure | Error you see | How to raise it |
|---|---|---|---|---|
| Python 3.12 | sys.getrecursionlimit() = 1000 | ~990 frames (plain function) | RecursionError | sys.setrecursionlimit(10**6); for very deep recursion also run inside threading.Thread after threading.stack_size(512 * 1024 * 1024) |
| Java 21 | thread stack size (-Xss), typically 1 MB on 64-bit platforms | ~30,000 frames | StackOverflowError | java -Xss512m, or new Thread(null, task, "main", 1L << 29).start() |
| C++17 | OS stack: 8 MB main thread on Linux and macOS, 1 MB on Windows | 100,000 ok, 1,000,000 crashed (unoptimised build) | segmentation fault, no message | ulimit -s unlimited (Linux), linker flag on Windows, or a thread with a larger stack |
| Node 24 (TypeScript) | V8 stack about 1 MB | ~8,900 frames | RangeError: Maximum call stack size exceeded | node --stack-size=… (risky: can crash the process instead of throwing) |
Two Python surprises found while testing: with the limit raised to 300,000, a hand-written dictionary memo recursed 100,000 deep without trouble, but the same function wrapped in @functools.lru_cache still failed beyond about 3,300 levels, because each cached call passes through C code that has its own, separate depth limit. Do not trust lru_cache for deep chains.
The practical rule: if the longest chain of subproblems can exceed a few thousand, tabulate. Coin change with a 1-cent coin and amount , LCS of two strings of length (chain length up to ), a path-graph tree DP with nodes — all of these crash a naive memo in at least one language. The implementation section below demonstrates this: the memoized version throws on amount 10,000 in Python and 100,000 in Java and TypeScript, while the table version handles a million.
Memoization versus tabulation
| Memoization (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| How you write it | The recursive definition plus a cache | Loops over states in a valid order |
| Order of states | Found automatically by the recursion | You must choose it (and can get it wrong) |
| States computed | Only those reachable from the question | All of them |
| Overhead per state | Function call, cache lookup | Array access |
| Deep chains | Risk of stack overflow (table above) | No recursion |
| Space optimisation | Hard (the cache keeps everything) | Easy (rolling arrays) |
| Sparse or weird state spaces (tuples, big numbers) | Natural with a hash map | Needs an index mapping |
| Best for | Getting a correct first version; sparse states; tree and DAG DPs | Production code, large inputs, memory-tight solutions |
Most people find memoization easier to derive because it is just the recursion. A good workflow: write the brute-force recursion, memoize it, confirm it matches brute force on small inputs, then convert to a table if you need speed, memory or depth. The conversion is mechanical: the memo's arguments become array indices, the base cases become initial values, and the order is "reverse of the recursion's dependency arrows".
Reconstructing the answer
A DP table stores values — "2 coins". Interviews and real systems usually want the solution — "3 + 3". Two standard ways to get it:
Parent pointers. When you write dp[a], also write which choice produced it (choice[a] = c). Afterwards, start at the answer state and follow the choices back to a base case. This costs one extra array of the same shape as the table. It is what the code in this lesson does.
Walk back by recomputing. Keep only the dp table. At the answer state, try every option and pick any one whose value matches: for coin change, any with . Move to that state and repeat. No extra memory, a little extra time ( per step). The grid-path reconstruction in Grid & Path DP works this way.
Either way, reconstruction needs the full table (or the full choice array). If you rolled the table down to one row to save memory, the information needed to walk back is gone. For two-sequence problems there is a clever way around this — Hirschberg's divide-and-conquer trick reconstructs an LCS or alignment in linear space — which Sequence DP covers.
flowchart LR
A6["a = 6, dp 2"] -->|"coin 3"| A3["a = 3, dp 1"]
A3 -->|"coin 3"| A0["a = 0, dp 0 (base)"]
Space optimisation: rolling arrays
If a state only reads states from the last "layers", you only need to keep layers. Fibonacci reads the two previous values, so two variables replace the whole array. A 2-D table where row reads only row (LCS, edit distance, 0/1 knapsack) can be kept as two rows — or even one, if you are careful about the direction you overwrite it.
The one-row trick is where bugs live, because overwriting changes what later cells read:
- 0/1 knapsack (each item at most once) with one row must loop capacity downward. Looping upward lets
dp[c - w]already include the current item, so the item gets used twice. With one item of weight 2 and value 6 and capacity 5, the upward loop reports 12 instead of 6. (DP Debugging shows a stress test catching exactly this.) - Unbounded knapsack and coin change (unlimited copies) loop upward, deliberately, for the same reason.
- LCS with one row must save the old diagonal value in a temporary variable before overwriting it.
Rolling arrays change memory from to and keep the time the same. You lose reconstruction (see above), so roll only when you need only the value.
Counting, optimisation and feasibility
The same state and the same "last decision" skeleton produce three different DPs depending on what you combine. Coin change with coins [1, 2, 5] and amount 5 shows all three:
| Question | Kind | Combine options with | Base value | Impossible value | Answer for [1, 2, 5], 5 |
|---|---|---|---|---|---|
| Fewest coins? | Optimisation | min of (option + 1) | 1 (just the 5) | ||
| How many ways (order ignored)? | Counting | sum | 0 | 4 | |
| Can it be paid at all? | Feasibility | or | $ok[0] = $ true | false | true |
The four ways are 5; 2+2+1; 2+1+1+1; 1+1+1+1+1. Two things in this table trip up beginners:
- Counting base case is 1, not 0. There is exactly one way to make 0: choose nothing. Set it to 0 and every count becomes 0.
- Order of loops decides what you count. With coins in the outer loop (
for c in coins: for a in …), each multiset is counted once: 4. With amounts outer and coins inner, ordered sequences are counted — 1+2+2 and 2+1+2 become different — and the answer is 9. Both are correct DPs for different questions (LeetCode 518 versus LeetCode 377). Know which one you are asked.
Mathematically the three kinds are the same algorithm over different "semirings": for counting, for shortest/cheapest, for feasibility. That is why a single state design usually serves all three, and why Counting DP and Matrix Exponentiation can reuse the same transition structure with a different pair of operations.
The framework applied: ten derivations
Each problem below is described in my own words, then derived with the five questions. Each one gets a full lesson later in the module; here the point is to see the same reasoning produce each algorithm. All example numbers were computed by running the DP.
1. Climbing stairs
Reach step taking 1 or 2 steps per move. Count the move sequences.
- State: = number of move sequences that end exactly on step .
- Transition: the last move was a 1-step from or a 2-step from : .
- Base: (the empty sequence), .
- Answer: . Order: increasing .
- Complexity: time; space with two variables.
- Example: gives 8; gives 89. These are Fibonacci numbers shifted by one.
Deep dive: 1-D DP.
2. Min cost climbing stairs
Step has a toll cost[i], paid when you step off it. You may start on step 0 or step 1, move up 1 or 2 each time, and finish just past the last step. Minimise the total toll.
- State: = cheapest total to stand on position (where is the top, past the last step).
- Transition: .
- Base: (you may start on either for free).
- Answer: . Order: increasing .
- Complexity: time, space.
- Example: cost = [10, 15, 20] gives 15 (start on step 1, pay 15, jump 2 to the top). cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] gives 6.
The state definition "cost to stand here, toll not yet paid" is a deliberate choice; defining it as "cost including this step's toll" also works but moves the off-by-one into the answer. Write the sentence down and stick to it.
3. Coin change: fewest coins
Given coin values (unlimited supply) and an amount, find the fewest coins summing exactly to the amount, or −1.
- State: = fewest coins summing to exactly ( if impossible).
- Transition: .
- Base: .
- Answer: , or −1 if infinite. Order: increasing .
- Complexity: time for coin values, space.
- Example: [1, 3, 4] and 6 gives 2 (3 + 3); [1, 2, 5] and 11 gives 3 (5 + 5 + 1); [2] and 3 gives −1.
Deep dive: Knapsack (this is unbounded knapsack with every value equal to 1).
4. Coin change: number of ways
Same coins and amount; count the multisets of coins that sum to the amount.
- State: = number of ways to make using only the first coin values.
- Transition: either use no coin of value , or use at least one: .
- Base: for all ; for .
- Answer: . Order: coins outer, amounts increasing inner — which also lets one row serve all .
- Complexity: time, space.
- Example: [1, 2, 5] and 5 gives 4. (If order mattered — amounts outer, coins inner — it would be 9.)
The extra index is what prevents counting 1+2+2 and 2+1+2 separately: by fixing that coins are considered in a fixed order, each multiset is built in exactly one way.
5. Unique paths in a grid
A robot on an grid moves only right or down from the top-left to the bottom-right. Count the routes.
- State: = number of routes from the start to cell .
- Transition: last move came from above or from the left: .
- Base: first row and first column are all 1.
- Answer: . Order: row by row, left to right.
- Complexity: time, space with one rolling row.
- Example: gives 10; gives 28 (both equal ).
Deep dive: Grid & Path DP.
6. Longest increasing subsequence,
Find the length of the longest strictly increasing subsequence (elements in order, not necessarily adjacent).
The tempting state " = LIS of the first elements" does not work: to extend it with element you would need to know the last value of that subsequence, which the state forgot. The fix is the most useful trick in sequence DP — anchor the state at its end:
- State: = length of the longest increasing subsequence that ends at index .
- Transition: (or 1 if no such ).
- Base: covered by the "or 1".
- Answer: — note it is not . Order: increasing .
- Complexity: time, space. (An method exists — the module overview's "patience sorting" code.)
- Example: [10, 9, 2, 5, 3, 7, 101, 18] gives = [1, 1, 1, 2, 2, 3, 4, 4], answer 4.
Deep dive: Sequence DP.
7. Longest common subsequence
Find the length of the longest sequence that is a subsequence of both strings and .
- State: = LCS length of the prefixes and .
- Transition: if , then ; otherwise .
- Base: (an empty prefix shares nothing).
- Answer: . Order: row by row.
- Complexity: time; space for the length only.
- Example: "ABCDE" and "ACE" gives 3.
Using prefix lengths (not last indices) as the state makes the empty prefix a real row and column, which removes most off-by-one bugs. Deep dives: Sequence DP, String DP.
8. 0/1 knapsack
Items have weights and values; each can be taken at most once; the total weight must not exceed . Maximise the total value.
- State: = best value using only the first items with capacity .
- Transition: skip item or take it (if it fits): .
- Base: .
- Answer: . Order: items outer; with one rolling row, capacity downward.
- Complexity: time, space. This is pseudo-polynomial: polynomial in the value , exponential in the number of bits used to write .
- Example: weights [1, 3, 4, 5], values [1, 4, 5, 7], gives 9 (items of weight 3 and 4).
Why the extra index ? Because "how much capacity is left" alone does not say which items are already used. The index is the past you need to remember. Deep dive: Knapsack.
9. Word break
Can string be split into a sequence of dictionary words?
- State: = true if the prefix can be split.
- Transition: — the last word is .
- Base: $B[0] = $ true (the empty prefix is split into zero words).
- Answer: . Order: increasing .
- Complexity: substring checks, each for hashing the substring, so worst case; limiting to or using a trie brings it down.
- Example: "leetcode" with {leet, code} gives true ( and are true); "catsandog" with {cats, dog, sand, and, cat} gives false.
Deep dive: String DP and Partition DP.
10. Partition equal subset sum
Can the array be split into two groups with equal sums?
Reduce first: the two groups must each sum to , where is the total. If is odd, the answer is no. Otherwise: is there a subset summing to ? That is a feasibility 0/1 knapsack.
- State: = true if some subset of the items seen so far sums to exactly .
- Transition: for each item , for from down to : .
- Base: $R[0] = $ true.
- Answer: . Order: items outer, downward (each item at most once).
- Complexity: time, space. A bitset makes it :
bits |= bits << x. - Example: [1, 5, 11, 5] gives true ({11} and {1, 5, 5}); [1, 2, 3, 5] gives false (the sum 11 is odd).
All ten at a glance
| # | Problem | State | Kind | States | Work per state | Time |
|---|---|---|---|---|---|---|
| 1 | Climbing stairs | counting | ||||
| 2 | Min cost climbing | optimisation | ||||
| 3 | Coin change (min) | optimisation | amount | |||
| 4 | Coin change (ways) | counting | amount × | |||
| 5 | Unique paths | counting | ||||
| 6 | LIS | ending at | optimisation | |||
| 7 | LCS | prefixes | optimisation | |||
| 8 | 0/1 knapsack | optimisation | ||||
| 9 | Word break | prefix | feasibility | checks | naive | |
| 10 | Partition equal sum | feasibility |
Three state shapes cover all ten: a position in one sequence (1, 2, 6, 9), positions in two sequences or a grid (5, 7), and a position plus a resource budget (3, 4, 8, 10). Most of the module is about adding one more idea to these shapes.
The ladder: brute force → better → optimal
Problem: fewest coins for amount using k coin values.
Rung 0 — greedy. Take the largest coin that fits, repeat. time. Correct for "canonical" systems like US coins (1, 5, 10, 25), wrong in general: [1, 3, 4] and 6 gives 3 coins instead of 2. Deciding whether a coin system is canonical is itself a nontrivial problem (Pearson gave a polynomial-time test in 2005). Greedy is not a rung of the ladder — it is the reason the ladder exists.
Rung 1 — plain recursion. without a cache. Correct, but it explores every ordered sequence of coins: the call tree can have up to about leaves. With coins [1, 2] the number of calls for amount is (a Fibonacci number again): 317,810 calls for amount 25 and 433,494,436 for amount 40, to answer questions about only 41 distinct amounts. Use it only as a brute-force oracle for tiny inputs.
Rung 2 — memoized recursion. Same function plus a cache. Each of the states is computed once with work: time, memory, plus a recursion depth up to . Better than rung 1 because each distinct question is answered once instead of once per path that reaches it.
Rung 3 — tabulation. Same time and memory, no recursion, so no stack limit, and with less constant overhead per state (an array access instead of a call and a cache lookup). Better than rung 2 because it removes the depth limit and the per-call cost.
Rung 4 — tabulation with reconstruction. One extra array of choices; same complexity. Better in what it returns: the coins, not just the count.
There is no rung 5 for general coin change: the problem is NP-hard when the amount is written in binary (it contains subset sum), so a truly polynomial algorithm is not expected; is pseudo-polynomial.
| Rung | Method | Time | Extra space | Why better than the rung above |
|---|---|---|---|---|
| 0 | Greedy | — (wrong on [1, 3, 4]) | ||
| 1 | Plain recursion | exponential | stack | Correct |
| 2 | Memoization | + stack | Each subproblem once | |
| 3 | Tabulation | No stack overflow, lower overhead | ||
| 4 | Table + parent pointers | Returns the actual coins |
Correctness
Every DP proof in this module has the same skeleton: induction over the order of computation.
Claim. When state is computed, its stored value equals the true answer for . Base. Base-case states are set by direct argument. Step. Every state reads only states that come earlier in the order. By the induction hypothesis, those values are correct. The transition, applied to correct inputs, gives the correct value for .
The order makes the induction well-founded; in memoization the recursion depth plays that role (a call returns only after the calls it made have returned). What remains in each problem is to prove the transition correct, which comes in two flavours:
For optimisation — exhaustiveness plus optimal substructure. For coin change: (1) Every way to pay has a last coin , so the options coins cover all solutions — none is missed. (2) Given that the last coin is , the best you can do is , by the cut-and-paste argument: any solution with last coin consists of a solution for plus one coin, and replacing that part with an optimal one can only help. (3) Each option is achievable (take an optimal solution for , add ). So the minimum over options is exactly the optimum.
For counting — a partition into disjoint, exhaustive cases. For climbing stairs: the sequences ending on step split by their last move into "last move 1" and "last move 2". The two groups are disjoint (different last moves) and exhaustive (no third kind of move). Removing the last move is a bijection from the first group to sequences ending at and from the second to sequences ending at . Hence . Counting DPs fail when the cases overlap (double counting) or miss something; "ways" for coin change with amounts outer and coins inner overcounts multisets precisely because the cases "last coin is " are not a partition of multisets.
For reconstruction. Following parent pointers from the answer state visits states whose stored choice achieved the optimum, so the choices assemble into a solution with exactly the optimal value. It terminates because each step moves to a strictly earlier state in the order.
Complexity
The rule: time = the sum, over all states, of the cost of that state's transition, which is usually (number of states) × (options per state). Space = number of states stored, or the size of the layers you keep.
| Quantity | Coin change (min) | How to read it |
|---|---|---|
| States | one per value of | |
| Options per state | one per coin value | |
| Time | best = average = worst (every state does all options) | |
| Space (table) | plus for choices if reconstructing | |
| Recursion depth (memo) | up to | why tabulation is safer |
Memoization can be faster than tabulation when only a small fraction of states is reachable from the question (for example a recursion on where only states with even are ever visited), and slower when all are reachable, because of call and hashing overhead.
Pseudo-polynomial time. When a dimension of the table is a number from the input (an amount, a capacity, a target sum) rather than a count of input items, the running time is polynomial in the number's value, not in its length in bits. Coin change with amount has a fine input size (a few dozen bytes) and a hopeless table. Seeing this early tells you when you need a different state (for example, swap the roles of value and weight in knapsack — the Knapsack lesson does this).
Budget check before coding. Multiply your states by your transitions. Around simple operations is about one second in C++ or Java, a few seconds in TypeScript, and far too slow in Python (aim for under about ). If the product is too big, the state has too many dimensions or the transition can be sped up — see DP Optimizations.
Implementation
Coin change four ways in each language: memoized (top-down), tabulated (bottom-up), tabulated with parent pointers to return the coins, and the counting version. Each program checks the examples from this lesson and then demonstrates the depth problem: the memoized version fails on a long chain of subproblems (amount 10,000 in Python, 100,000 in Java and TypeScript) while the table version is unaffected. The C++ program skips that demonstration, because overflowing the stack in C++ crashes the process instead of raising an exception it could catch.
import sys
from functools import lru_cache
from typing import List, Optional
INF = float("inf")
def min_coins_memo(coins: List[int], amount: int) -> int:
"""Top-down: f(a) = fewest coins summing to a, or INF if impossible."""
@lru_cache(maxsize=None)
def f(a: int) -> float:
if a == 0:
return 0 # base case: zero coins make zero
best = INF
for c in coins:
if c <= a:
best = min(best, f(a - c) + 1)
return best
ans = f(amount)
return -1 if ans == INF else int(ans)
def min_coins_tab(coins: List[int], amount: int) -> int:
"""Bottom-up: fill dp[0..amount] left to right."""
dp = [0] + [INF] * amount # dp[0] = 0 is the base case
for a in range(1, amount + 1): # order: every a - c < a is already final
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return -1 if dp[amount] == INF else int(dp[amount])
def min_coins_with_coins(coins: List[int], amount: int) -> Optional[List[int]]:
"""Bottom-up plus a parent pointer: choice[a] = the coin used last for a."""
dp = [0] + [INF] * amount
choice = [0] * (amount + 1)
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]: # strict '<' keeps the first best coin
dp[a] = dp[a - c] + 1
choice[a] = c
if dp[amount] == INF:
return None
used, a = [], amount
while a > 0: # walk the parent pointers back to 0
used.append(choice[a])
a -= choice[a]
return used
def count_ways(coins: List[int], amount: int) -> int:
"""Counting DP: number of multisets of coins summing to amount (order ignored)."""
ways = [1] + [0] * amount # one way to make 0: take nothing
for c in coins: # coins outer => each multiset counted once
for a in range(c, amount + 1):
ways[a] += ways[a - c]
return ways[amount]
if __name__ == "__main__":
assert min_coins_memo([1, 3, 4], 6) == 2
assert min_coins_tab([1, 3, 4], 6) == 2
assert min_coins_with_coins([1, 3, 4], 6) == [3, 3]
assert min_coins_tab([2], 3) == -1 and min_coins_memo([2], 3) == -1
assert min_coins_with_coins([2], 3) is None
assert min_coins_tab([1, 2, 5], 11) == 3
assert min_coins_with_coins([1, 2, 5], 11) == [1, 5, 5]
assert min_coins_tab([7], 0) == 0
assert count_ways([1, 2, 5], 5) == 4
# Memo on a big amount hits Python's default recursion limit (1000);
# the table does not care.
assert min_coins_tab([1], 10_000) == 10_000
try:
min_coins_memo([1], 10_000)
print("memo survived (recursion limit was raised?)")
except RecursionError:
print("memo: RecursionError at amount 10000, as expected")
print("coin change: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CoinChange {
static final int INF = Integer.MAX_VALUE / 2; // big, but INF + 1 cannot overflow
// Top-down: memo[a] == -2 means "not computed yet".
static int minCoinsMemo(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2);
int ans = f(coins, amount, memo);
return ans >= INF ? -1 : ans;
}
private static int f(int[] coins, int a, int[] memo) {
if (a == 0) return 0; // base case
if (memo[a] != -2) return memo[a];
int best = INF;
for (int c : coins) {
if (c <= a) best = Math.min(best, f(coins, a - c, memo) + 1);
}
return memo[a] = best;
}
// Bottom-up: fill dp[0..amount] left to right.
static int minCoinsTab(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
}
}
return dp[amount] >= INF ? -1 : dp[amount];
}
// Bottom-up plus parent pointers; returns null when impossible.
static List<Integer> minCoinsWithCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int[] choice = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
choice[a] = c;
}
}
}
if (dp[amount] >= INF) return null;
List<Integer> used = new ArrayList<>();
for (int a = amount; a > 0; a -= choice[a]) used.add(choice[a]);
return used;
}
// Counting DP: multisets of coins that sum to amount.
static long countWays(int[] coins, int amount) {
long[] ways = new long[amount + 1];
ways[0] = 1;
for (int c : coins) {
for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
}
return ways[amount];
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(minCoinsMemo(new int[]{1, 3, 4}, 6) == 2, "memo 6");
check(minCoinsTab(new int[]{1, 3, 4}, 6) == 2, "tab 6");
check(minCoinsWithCoins(new int[]{1, 3, 4}, 6).equals(List.of(3, 3)), "coins 6");
check(minCoinsTab(new int[]{2}, 3) == -1 && minCoinsMemo(new int[]{2}, 3) == -1, "impossible");
check(minCoinsWithCoins(new int[]{2}, 3) == null, "impossible coins");
check(minCoinsTab(new int[]{1, 2, 5}, 11) == 3, "tab 11");
check(minCoinsWithCoins(new int[]{1, 2, 5}, 11).equals(List.of(1, 5, 5)), "coins 11");
check(minCoinsTab(new int[]{7}, 0) == 0, "zero");
check(countWays(new int[]{1, 2, 5}, 5) == 4, "ways");
check(minCoinsTab(new int[]{1}, 100_000) == 100_000, "big tab");
try {
minCoinsMemo(new int[]{1}, 100_000);
System.out.println("memo survived");
} catch (StackOverflowError e) {
System.out.println("memo: StackOverflowError at amount 100000, as expected");
}
System.out.println("coin change: all tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <optional>
#include <vector>
using namespace std;
const int INF = INT_MAX / 2; // INF + 1 must not overflow
// Top-down: memo[a] == -2 means "not computed yet".
int f(const vector<int>& coins, int a, vector<int>& memo) {
if (a == 0) return 0; // base case
if (memo[a] != -2) return memo[a];
int best = INF;
for (int c : coins)
if (c <= a) best = min(best, f(coins, a - c, memo) + 1);
return memo[a] = best;
}
int minCoinsMemo(const vector<int>& coins, int amount) {
vector<int> memo(amount + 1, -2);
int ans = f(coins, amount, memo);
return ans >= INF ? -1 : ans;
}
// Bottom-up: fill dp[0..amount] left to right.
int minCoinsTab(const vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for (int a = 1; a <= amount; ++a)
for (int c : coins)
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
return dp[amount] >= INF ? -1 : dp[amount];
}
// Bottom-up plus parent pointers; nullopt when impossible.
optional<vector<int>> minCoinsWithCoins(const vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INF), choice(amount + 1, 0);
dp[0] = 0;
for (int a = 1; a <= amount; ++a)
for (int c : coins)
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
choice[a] = c;
}
if (dp[amount] >= INF) return nullopt;
vector<int> used;
for (int a = amount; a > 0; a -= choice[a]) used.push_back(choice[a]);
return used;
}
// Counting DP: multisets of coins that sum to amount.
long long countWays(const vector<int>& coins, int amount) {
vector<long long> ways(amount + 1, 0);
ways[0] = 1;
for (int c : coins)
for (int a = c; a <= amount; ++a) ways[a] += ways[a - c];
return ways[amount];
}
int main() {
assert(minCoinsMemo({1, 3, 4}, 6) == 2);
assert(minCoinsTab({1, 3, 4}, 6) == 2);
assert((*minCoinsWithCoins({1, 3, 4}, 6) == vector<int>{3, 3}));
assert(minCoinsTab({2}, 3) == -1 && minCoinsMemo({2}, 3) == -1);
assert(!minCoinsWithCoins({2}, 3).has_value());
assert(minCoinsTab({1, 2, 5}, 11) == 3);
assert((*minCoinsWithCoins({1, 2, 5}, 11) == vector<int>{1, 5, 5}));
assert(minCoinsTab({7}, 0) == 0);
assert(countWays({1, 2, 5}, 5) == 4);
assert(minCoinsTab({1}, 1000000) == 1000000); // the table never recurses
cout << "coin change: all tests passed\n";
}
// Top-down: f(a) = fewest coins summing to a, Infinity if impossible.
function minCoinsMemo(coins: number[], amount: number): number {
const memo = new Map<number, number>();
const f = (a: number): number => {
if (a === 0) return 0; // base case
const hit = memo.get(a);
if (hit !== undefined) return hit;
let best = Infinity;
for (const c of coins) {
if (c <= a) best = Math.min(best, f(a - c) + 1);
}
memo.set(a, best);
return best;
};
const ans = f(amount);
return ans === Infinity ? -1 : ans;
}
// Bottom-up: fill dp[0..amount] left to right.
function minCoinsTab(coins: number[], amount: number): number {
const dp = new Array<number>(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Bottom-up plus parent pointers; null when impossible.
function minCoinsWithCoins(coins: number[], amount: number): number[] | null {
const dp = new Array<number>(amount + 1).fill(Infinity);
const choice = new Array<number>(amount + 1).fill(0);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
choice[a] = c;
}
}
}
if (dp[amount] === Infinity) return null;
const used: number[] = [];
for (let a = amount; a > 0; a -= choice[a]) used.push(choice[a]);
return used;
}
// Counting DP: multisets of coins that sum to amount.
function countWays(coins: number[], amount: number): number {
const ways = new Array<number>(amount + 1).fill(0);
ways[0] = 1;
for (const c of coins) {
for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
}
return ways[amount];
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
check(minCoinsMemo([1, 3, 4], 6) === 2, "memo 6");
check(minCoinsTab([1, 3, 4], 6) === 2, "tab 6");
check(JSON.stringify(minCoinsWithCoins([1, 3, 4], 6)) === "[3,3]", "coins 6");
check(minCoinsTab([2], 3) === -1 && minCoinsMemo([2], 3) === -1, "impossible");
check(minCoinsWithCoins([2], 3) === null, "impossible coins");
check(minCoinsTab([1, 2, 5], 11) === 3, "tab 11");
check(JSON.stringify(minCoinsWithCoins([1, 2, 5], 11)) === "[1,5,5]", "coins 11");
check(minCoinsTab([7], 0) === 0, "zero");
check(countWays([1, 2, 5], 5) === 4, "ways");
check(minCoinsTab([1], 100_000) === 100_000, "big tab");
try {
minCoinsMemo([1], 100_000);
console.log("memo survived");
} catch (e) {
console.log("memo: RangeError (stack) at amount 100000, as expected");
}
console.log("coin change: all tests passed");
Notes on the language choices:
- Infinity. Python and TypeScript have a real infinity, and
inf + 1 == inf. Java and C++ do not, so they useINT_MAX / 2: large enough to lose every comparison, small enough thatINF + 1does not overflow into a negative number. UsingInteger.MAX_VALUEitself would makedp[a - c] + 1wrap to the most negative integer and win everymin— a classic bug. - The memo's "not computed" marker must be a value no real answer can take. Here −2 is safe; 0 or −1 would not be (0 is a real answer, and some people use −1 to mean "impossible").
- Counting uses 64-bit integers (
long,long long). Coin-change counts grow fast; for large amounts problems ask for the count modulo , and you add% MODafter each addition.
Real-world uses
DP is not an interview curiosity; it is inside software you use daily.
- Routing. The Bellman-Ford recurrence — "my distance to is the minimum over neighbours of (link cost + their distance to )" — is a DP over the number of hops, and it is exactly what distance-vector routing protocols such as RIP compute in a distributed way (RFC 2453). See Shortest Paths.
- Decoding noisy signals. The Viterbi algorithm (Andrew Viterbi, 1967) finds the most likely sequence of hidden states in a hidden Markov model by a DP over time steps. It decodes convolutional codes in digital radio and satellite links and underlies classic speech recognisers and part-of-speech taggers.
- Diff and version control.
diffand Git compute a shortest edit script between two files, which is the LCS / edit-distance DP; production tools use Myers' 1986 refinement that explores only the states near the diagonal. See String DP. - Bioinformatics. Needleman–Wunsch (1970) and Smith–Waterman (1981) align DNA and protein sequences with a grid DP. See Grid & Path DP.
- Typesetting. TeX breaks paragraphs into lines by minimising a total "badness" over all possible break points with a DP (Knuth and Plass, "Breaking Paragraphs into Lines", 1981), rather than greedily filling each line — which is why TeX paragraphs avoid the very loose last-but-one lines that greedy wrapping produces.
- Database query optimisers. IBM's System R (Selinger et al., 1979) chose join orders by a DP over subsets of tables, keeping the cheapest plan per subset; PostgreSQL's planner still uses this approach for queries with fewer than
geqo_threshold(default 12) tables, switching to a genetic search above that. This is a bitmask DP — see Bitmask DP. - Spell checking and fuzzy search. Edit distance ranks suggestions; see the module overview.
Pitfalls & edge cases
- Vague state. "dp[i] = the answer for i" is not a state. Write which prefix, ending where, with how much budget left, and whether it is "exactly" or "at most". Half of all DP bugs disappear when the sentence is precise.
- Base case wrong by one. Climbing stairs with instead of 1 shifts the whole sequence and gives 5 for instead of 8. Counting DPs almost always need "one way to do nothing".
- Sentinel overflow.
Integer.MAX_VALUE + 1is negative. UseMAX/2, or check for INF before adding. - "Not computed" equals a real answer. Initialising a memo with 0 when 0 is a legitimate value makes every state look cached.
- Iteration order that reads unfinished states. Interval DPs that loop the left end upward read rows that are still zero. Fill in an order that matches the dependency arrows.
- Rolling arrays in the wrong direction. 0/1 knapsack must go downward, unbounded upward.
- Amount 0, empty input. Coin change with amount 0 should return 0 coins, not −1. The code above handles it because the loop does not run and .
- Deep recursion. Table above. Tabulate when chains can exceed a few thousand.
- Answer state is not the last cell. LIS takes a max over all endings; "best path ending anywhere" problems do the same.
- Large counts. Use 64-bit or the modulus; in Python counts never overflow but get slow when they have thousands of digits.
The full catalogue, with a stress-test harness that catches most of these automatically, is in DP Debugging & How to Find the State.
Variations
- Pull versus push. The DPs above "pull": each state reads its predecessors. You can also "push": each finished state adds its contribution to its successors (
dp[a + c] = min(dp[a + c], dp[a] + 1)). Pushing is natural for probability and reachability DPs, and when successors are easier to enumerate than predecessors. - Forward versus backward. The state can mean "best from the start to here" or "best from here to the end". Both work for most problems; the Grid & Path DP dungeon game shows a case where only the backward one is valid.
- Memoization with a hash map. When states are tuples, strings or large sparse numbers, a dictionary memo is the natural form; Digit DP and Game DP often use one.
- DP over a DAG given explicitly. If the input is already a DAG, process vertices in topological order — see DAG DP and Topological Sort.
- States that are sets. When the past must remember which items are used and , a bitmask is the state — Bitmask DP.
- Linear recurrences with huge . cannot be tabulated, but a fixed-size linear recurrence can be written as a matrix power and computed in multiplications — Matrix Exponentiation.
Practice ladder
Each problem is described in my own words; follow the link for the full statement. Do them in order: the first eight are the ten derivations above, the rest stretch the same framework.
1. Climbing Stairs (LeetCode 70) — Count the 1-or-2-step sequences to the top.
Hint
Derivation 1. Two variables suffice.
2. Min Cost Climbing Stairs (LeetCode 746) — Cheapest toll to get past the last step.
Hint
Derivation 2. Decide whether a step's toll is paid when you stand on it or when you leave it, and write that in your state sentence.
3. Frog 1 (AtCoder Educational DP Contest A) — A frog jumps 1 or 2 stones ahead, paying the height difference; minimise the total.
Hint
Same shape as min cost climbing: .
4. House Robber (LeetCode 198) — Maximise the sum of chosen houses with no two adjacent.
Solution
State: = most money from the first houses. The last house is either skipped () or robbed, in which case the one before it is skipped ().
def rob(nums):
prev2, prev1 = 0, 0 # best(i-2), best(i-1)
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
assert rob([2, 7, 9, 3, 1]) == 12 # 2 + 9 + 1
assert rob([]) == 0
time, space.
5. Coin Change (LeetCode 322) — Fewest coins for an amount.
Hint
Derivation 3; the implementation above is a full solution.
6. Coin Change II (LeetCode 518) — Number of coin multisets that make the amount.
Hint
Derivation 4. Coins in the outer loop.
7. Unique Paths (LeetCode 62) — Right/down routes across a grid.
Hint
Derivation 5, or .
8. Dice Combinations (CSES 1633) — Count ordered sequences of die rolls (1–6) summing to , modulo .
Solution
Order matters here, so it is the "amounts outer" counting DP: , .
MOD = 10**9 + 7
def dice_combinations(n):
ways = [1] + [0] * n
for s in range(1, n + 1):
ways[s] = sum(ways[s - d] for d in range(1, 7) if d <= s) % MOD
return ways[n]
assert dice_combinations(3) == 4 # 1+1+1, 1+2, 2+1, 3
assert dice_combinations(6) == 32
time.
9. Coin Combinations I (CSES 1635) and Coin Combinations II (CSES 1636) — The same coins, counted as ordered sequences (I) and as multisets (II).
Hint
Solve both and swap only the loop order. If your answers for I and II agree on [2, 3, 5] and 9, one of them is wrong (I gives 8, II gives 3).
10. Longest Increasing Subsequence (LeetCode 300) — Derivation 6.
Hint
"Ending at ", and the answer is the max over all . Then read the overview's version.
11. Longest Common Subsequence (LeetCode 1143) — Derivation 7.
Hint
Index by prefix lengths so row 0 and column 0 are the empty prefix.
12. Word Break (LeetCode 139) — Derivation 9.
Hint
is true. Only try $j \ge i - $ (longest word length).
13. Partition Equal Subset Sum (LeetCode 416) — Derivation 10.
Solution
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
reach = [True] + [False] * target # reach[c]: some subset sums to c
for x in nums:
for c in range(target, x - 1, -1): # downward: each number used once
reach[c] = reach[c] or reach[c - x]
return reach[target]
assert can_partition([1, 5, 11, 5]) is True
assert can_partition([1, 2, 3, 5]) is False
time, space.
14. Knapsack 1 (AtCoder Educational DP Contest D) — Classic 0/1 knapsack with capacity up to .
Hint
Derivation 8, one row, capacity downward, 64-bit values.
15. Removing Digits (CSES 1637) — Repeatedly subtract one of the number's own digits; fewest steps to reach 0.
Hint
. A state's options depend on the state itself — still a DP, because .
Common mistakes & interview follow-ups
"Why is this DP and not greedy?" Give the counterexample: [1, 3, 4] and 6. Greedy gives 3 coins, the optimum is 2. One concrete counterexample beats any amount of hand-waving.
"Top-down or bottom-up — which do you prefer?" Say both are ; top-down is easier to derive and only touches reachable states; bottom-up avoids recursion limits (quote the rough limits: about 1,000 in Python, around ten thousand frames in Java and Node), has lower overhead, and allows rolling arrays.
"Can you return the coins, not just the count?" Parent pointers or walk back; mention that it needs the full table.
"Reduce the memory." For coin change the table is already one-dimensional. For 2-D tables, keep one or two rows and explain what is lost (reconstruction) and which direction to loop.
"What if the amount is ?" The table is too big. Discuss: the problem is pseudo-polynomial; for special coin systems greedy may be provably optimal; otherwise there is no general fast method.
"Count the ways modulo ." Add % MOD after each addition; in Java/C++ keep values in 64-bit before taking the remainder.
"What is the time complexity, exactly?" States × transitions, stated with the variables of the problem — not "" when the table is amount × coins.
Mistakes interviewers watch for: no clear state sentence; using a greedy without proof; base case 0 for counting; INF overflow in Java/C++; forgetting the impossible case (−1); confusing combinations with permutations.
Quick quiz
1. Naive fib(10) makes how many calls, and how many distinct subproblems are there?
Answer
177 calls (), 11 distinct subproblems ( to ).
2. In the coin-change trace, why is even though no single coin is 5?
Answer
5 = 4 + 1 (or 1 + 4): the options at are , and , so the minimum is 2.
3. What is the base case for counting coin-change ways, and why?
Answer
: the empty selection is exactly one way to make 0. With 0 every count stays 0.
4. With coins [1, 2, 5] and amount 5, which loop order gives 4 and which gives 9?
Answer
Coins outer, amounts inner counts multisets: 4. Amounts outer, coins inner counts ordered sequences: 9.
5. Why is the LIS state "ending at " rather than "within the first "?
Answer
To extend a subsequence you must know its last value. "Ending at " fixes the last value to ; "within the first " forgets it.
6. A memoized solution works for amount 1,000 but crashes for amount 100,000 in Java. Why, and what is the fix?
Answer
The recursion depth reaches about 100,000 frames, exceeding the default thread stack. Tabulate (or run on a thread with a larger stack).
7. Is for knapsack a polynomial-time algorithm?
Answer
No — it is pseudo-polynomial. can be exponential in the number of bits used to write it.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., Chapter 14 — rod cutting, matrix-chain, LCS, the elements of DP (§14.3: optimal substructure, overlapping subproblems, the longest-simple-path counterexample, reconstruction).
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005), Chapter 6 — weighted interval scheduling as the first DP, subset sum and knapsack, sequence alignment.
- Jeff Erickson, Algorithms (2019), Chapter 3 "Dynamic Programming" — free at jeffe.cs.illinois.edu/teaching/algorithms; excellent on deriving recurrences from backtracking.
- Steven Skiena, The Algorithm Design Manual, 3rd ed. (2020), Chapter 10.
- Richard Bellman, Dynamic Programming (Princeton University Press, 1957), and Eye of the Hurricane: An Autobiography (1984) for the origin of the name.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — the shortest-path chapter for DP on DAGs.
- cp-algorithms, Introduction to Dynamic Programming.
- Python documentation,
sys.setrecursionlimitandfunctools.lru_cache. - David Pearson, "A polynomial-time algorithm for the change-making problem", Operations Research Letters 33(3), 2005.
- Donald E. Knuth and Michael F. Plass, "Breaking Paragraphs into Lines", Software: Practice and Experience 11(11), 1981.
- P. Griffiths Selinger et al., "Access Path Selection in a Relational Database Management System", SIGMOD 1979.
Lessons: previous — Dynamic Programming (module overview) · next — 1-D DP · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Recursion & Mathematical Induction · Backtracking & Recursion · Greedy Algorithms · Topological Sort · Shortest Paths · Grid & Path DP · String DP · DP Debugging.