Dynamic programming, step by step
Dynamic programming is recursion that writes its answers down. When a problem breaks into smaller versions of itself, and the same smaller versions keep coming back, solving each one once and storing it turns exponential work into a table filled in the right order. Each tab fills one table on a small example — the cells, the arrows to where each value came from, and the highlighted line of C++ move together — and every program compiles as-is. You can type your own input into any of them. The last tab is a Google onsite question solved the same way: best traveling route.
Climbing stairs: why the memo matters
O(1.6n) calls → O(n) with a memoLC 70 asks how many ways there are to climb n stairs, taking 1 or 2 at a time. The last move was either 1 stair or 2, so ways(n) = ways(n − 1) + ways(n − 2): a correct one-line recursion that is hopelessly slow, because it solves the same small problems again and again. Switch the memo off and on and watch the tree: the same answer from 25 calls, or from 11.
the recipe
- state
ways(k): the number of ways to climb k stairs.- choice
- The last move: 1 stair, leaving
ways(k - 1), or 2, leavingways(k - 2). - base
ways(0) = ways(1) = 1.- order
- Smaller k first. The recursion gets that by itself; a table gets it with a loop.
- answer
ways(n).
why the memo works
The tree for ways(6) calls ways(4) twice, ways(3) three times and ways(2) five times — Fibonacci numbers again. Those repeats are overlapping subproblems, and ways(k) is the same number whoever asks for it, so it can be stored the first time and handed back after that. With the memo every ways(k) is worked out once, and the other calls for it return at once: 2n − 1 calls.
cost
Without the memo, the call count grows like the Fibonacci numbers themselves, about 1.6n: ways(40) makes 331 million calls. With it, O(n) calls and O(n) memory for the memo and the call stack. The loop below needs no recursion at all, and since it only ever reads the last two values, two variables are enough.
without recursion
Bottom-up fills every answer from the smallest up. It can't overflow the call stack, and it makes the memory easy to cut.
watch out
- A memo only works if a subproblem's answer is the same whoever asks. If it depends on the path taken so far, that part of the path belongs in the state.
- The memo needs a “not computed yet” marker that can't be a real answer. 0 is safe here because ways(k) ≥ 1; for answers that can be 0, use −1.
- Top-down (recursion + memo) only solves the subproblems it actually reaches; bottom-up solves all of them, in an order you choose.
- The answers grow exponentially, so for big n problems ask for them modulo 109 + 7.
practice
- 70Climbing Stairs — this tab
- 509Fibonacci Number
- 746Min Cost Climbing Stairs — a min instead of a sum
- 91Decode Ways — the same shape, with rules on each step
- 62Unique Paths — the same idea on a grid
House robber: take it or leave it
O(n) time · O(1) memory possibleLC 198: houses along a street hold some money, and robbing two neighbors sets off the alarm. Greedy fails — the richest house can block two good ones — but every house has only two options, and either one leaves a smaller copy of the same problem.
the recipe
- state
dp[i]: the most money from the first i houses.- choice
- Leave house i − 1:
dp[i - 1]. Or rob it, so its left neighbor is left alone:a[i - 1] + dp[i - 2]. - base
dp[0] = 0; for the first house,dp[i - 2]counts as 0.- order
- Left to right.
- answer
dp[n]. Walk back to see which houses: wheredp[i]differs fromdp[i - 1], house i − 1 was robbed.
why it works
A best plan for the first i houses either robs house i − 1 or doesn't. If not, the rest of it is a best plan for i − 1 houses. If it does, the rest is a best plan for i − 2 houses. Only those totals matter, not how they were reached — that is optimal substructure, the second thing DP needs.
cost
One pass: O(n). Each dp[i] reads only the two before it, so two variables are enough for the total; naming the houses needs the whole array, or one bit per house.
houses in a circle
watch out
- Greedy gets this example wrong. Biggest first takes 7, then 6, then 4: 17. Every other house gives 12 or 14. The table finds 6 + 7 + 3 + 3 = 19.
- When leaving and robbing tie, either is right; this walk back prefers leaving.
- A circle of houses (LC 213) is two streets: one without the first house, one without the last.
- Houses on a tree (LC 337): keep two answers per node, with it and without it — the tree DP on the P vs NP page.
practice
- 198House Robber — this tab
- 213House Robber II — a circle
- 337House Robber III — a tree
- 740Delete and Earn — bucket the values, then rob
- 2140Solving Questions With Brainpower
Coin change: the fewest coins
O(amount × coins) time · O(amount) memoryLC 322: pay an amount with as few coins as possible, using each coin value as often as you like. Biggest coin first works for real currencies but not in general: with coins 1, 3 and 4 it pays 6 as 4 + 1 + 1, while 3 + 3 needs two.
the recipe
- state
dp[a]: the fewest coins that pay exactly a.- choice
- The last coin paid, c. Then
a - cis left, paid the same way:dp[a - c] + 1. - base
dp[0] = 0; every other amount starts at ∞, “can't pay it”.- order
- Amounts upward.
- answer
dp[amount], or −1 if it stayed ∞.
why it works
Take the last coin off a best way to pay a: what's left is a best way to pay a − c, or there would be a cheaper way to pay a. So trying every coin as the last one, on top of an amount that is already solved, can't miss the best.
cost
amount × coins steps. The amount is a number, not a count of things, so this is pseudo-polynomial: fine up to 104–105, hopeless at 1018. The P vs NP page explains why that matters.
counting the ways instead
watch out
- Use a big “∞” that has room: with INT_MAX,
dp[a - c] + 1overflows. INT_MAX / 2 is safe. - Combinations (LC 518) and orderings (LC 377) differ only in which loop is outside: coins outside counts 1 + 2 once, amounts outside counts 1 + 2 and 2 + 1.
- To list the coins, walk back: any coin with
dp[a - c] + 1 == dp[a]is a valid last coin. - Each coin once instead of unlimited? That is the 0/1 knapsack.
practice
- 322Coin Change — this tab
- 518Coin Change II — count combinations
- 377Combination Sum IV — count orderings
- 279Perfect Squares — the coins are 1, 4, 9, …
- 983Minimum Cost For Tickets
Longest increasing subsequence
O(n²) here · O(n log n) with binary searchLC 300: the longest strictly increasing run you can pick out of an array, keeping the order but skipping freely. Trying every subset is 2n. Asking “what is the longest run that ends right here?” at every position is n2.
the recipe
- state
len[i]: the longest increasing subsequence that ends with a[i].- choice
- Which earlier, smaller a[j] comes right before it:
len[j] + 1.prev[i]remembers that j. - base
len[i] = 1: a[i] on its own.- order
- Left to right.
- answer
- The largest
len[i]anywhere — not the last one. Followprev[]back to rebuild it.
why it works
Take a longest run ending at a[i] and remove a[i]: what's left ends at some smaller a[j] before it, and it must be a longest run ending there — a longer one would make the original longer too. So len[i] is 1 + the best len[j] over the smaller values before it.
cost
Every i looks back at every j: about n2/2 comparisons, fine for a few thousand numbers. For 105, keep for each length the smallest number a run of that length can end with, and binary-search where each new number goes:
watch out
- The answer is the maximum over all i, not
len[n - 1]: the longest run can end anywhere. - Strictly increasing uses
lower_boundin the fast version; non-decreasing usesupper_bound. - The fast version's
tailshas the right length but usually isn't a real subsequence. To print one, store a parent index for every element. - Nesting in two dimensions (LC 354): sort by width, ties by height descending, then run LIS on the heights.
practice
- 300Longest Increasing Subsequence — this tab
- 354Russian Doll Envelopes — sort, then LIS
- 673Number of Longest Increasing Subsequence
- 1671Minimum Number of Removals to Make Mountain Array — LIS from both ends
- 1964Find the Longest Valid Obstacle Course at Each Position
0/1 knapsack
O(n × W) time · O(W) memory with one rowPack items with weights and values into a bag that holds weight W, each item at most once, for the most value. Packing by value per weight gets 8 here; the best is 9. Row by row, the table tries each item in every amount of room there could be.
the recipe
- state
dp[i][c]: the most value from the first i items, with room c.- choice
- Leave item i − 1:
dp[i - 1][c]. Or pack it, if it fits:v + dp[i - 1][c - w]. - base
- Row 0, no items yet: all 0.
- order
- Item by item; within a row, any order.
- answer
dp[n][W]. Walking back, a value that differs from the one above it means that item was packed.
why it works
In a best packing of the first i items, the last one is either in or out. Out: the rest is a best packing of i − 1 items in the same room. In: the rest is a best packing of i − 1 items in the room it leaves. The row above has both, for every room.
cost
n × (W + 1) cells, O(1) each. W is a number, so this is pseudo-polynomial; the P vs NP page explains why that doesn't make knapsack easy.
one row
watch out
- With one row, go through the rooms downward. Upward reads values this item has already changed, and packs it again — that is the unbounded knapsack, coin change.
- “Exactly W” instead of “at most W”: start every room except 0 at −∞.
- Room in the billions but few items: swap the roles (dp over value, keeping the least weight) or meet in the middle.
practice
- 416Partition Equal Subset Sum — values only
- 494Target Sum
- 474Ones and Zeroes — two budgets
- 1049Last Stone Weight II
- 879Profitable Schemes
Longest common subsequence
O(n × m) time · two rows for the lengthLC 1143: the longest sequence of letters that appears, in order, in both strings — STONE and LONGEST share ONE. The table compares every prefix of one with every prefix of the other, and each cell only looks at its neighbors up and to the left.
the recipe
- state
dp[i][j]: the LCS length of the first i letters of a and the first j of b.- choice
- Same last letter: keep it,
dp[i - 1][j - 1] + 1. Different: one of them is not in the answer,max(dp[i - 1][j], dp[i][j - 1]). - base
- An empty prefix has nothing in common: row 0 and column 0 are 0.
- order
- Row by row, left to right.
- answer
dp[n][m]; walk back from the corner to spell it.
why it works
If the last letters are equal, some longest common subsequence ends with that letter, so matching them loses nothing. If they differ, they can't both be the last letter of the same common subsequence, so dropping one — whichever leaves more — is safe.
cost
n × m cells, O(1) each. Each row only reads the one above, so the length needs two rows; spelling the answer needs the whole table, or Hirschberg's divide and conquer for O(n + m) memory.
watch out
- Subsequence, not substring: letters may be skipped. For the longest common substring, a match gives
dp[i - 1][j - 1] + 1, a mismatch gives 0, and the answer is the largest cell anywhere. - Off by one: the table is (n + 1) × (m + 1), and
a[i - 1]is the i-th letter. - Many string questions are this table in disguise: the fewest deletions that make two strings equal (LC 583) is n + m − 2 × LCS.
practice
- 1143Longest Common Subsequence — this tab
- 583Delete Operation for Two Strings
- 712Minimum ASCII Delete Sum for Two Strings
- 1092Shortest Common Supersequence — walk the table back
- 516Longest Palindromic Subsequence — LCS with the reverse
Edit distance
O(n × m) time · two rows for the numberLC 72: the fewest one-letter inserts, deletes and replaces that turn one word into another — horse into ros takes three. It is the LCS table with costs: every cell is the cheapest of three ways to get there.
the recipe
- state
dp[i][j]: the edits that turn the first i letters of a into the first j of b.- choice
- Equal last letters: free,
dp[i - 1][j - 1]. Otherwise 1 + the cheapest of replace (dp[i - 1][j - 1]), delete a's letter (dp[i - 1][j]), insert b's letter (dp[i][j - 1]). - base
dp[i][0] = ideletes;dp[0][j] = jinserts.- order
- Row by row.
- answer
dp[n][m]; walking back names the edits.
why it works
Look at what happens to the last letters in a best edit script: a's last letter is deleted, or b's last letter is inserted, or one becomes the other (free if they are already equal). Each case leaves a smaller pair of prefixes to fix — as cheaply as possible.
cost
n × m cells, O(1) each; two rows if only the number is needed.
watch out
- Equal letters cost 0 and go diagonally. Don't add 1 for them, and don't bother with the other two options there: keeping a matching letter never hurts.
- Different costs per operation only change the three +1s.
- “One edit apart?” (LC 161) needs no table: walk both strings once.
practice
- 72Edit Distance — this tab
- 161One Edit Distance
- 1035Uncrossed Lines — LCS again
- 97Interleaving String
- 115Distinct Subsequences — count instead of minimize
Burst balloons: DP over intervals
O(n³) time · O(n²) memoryLC 312: bursting a balloon pays its number times its two current neighbors, and then those neighbors become neighbors. Deciding what to burst first is a mess, because every burst changes who stands next to whom. Deciding what to burst last is clean: until then that balloon stays put and splits the row into two halves that never touch.
the recipe
- state
dp[l][r]: the most coins from bursting every balloon strictly between l and r, with l and r still standing.- choice
- k, the last balloon burst in that gap: it pays
a[l] * a[k] * a[r], plusdp[l][k]anddp[k][r]. - base
- Neighbors (r = l + 1) have nothing between them: 0. A 1 at each end acts as a wall.
- order
- By gap length, short gaps first.
- answer
dp[0][n - 1].
why it works
While k is still there, nothing on its left is ever next to anything on its right, so the two sides are separate problems. When k finally goes, its only neighbors can be l and r. Trying every k as the last one covers every possible order.
cost
About n2/2 gaps with up to n choices each: O(n³), 2.7·107 steps for LeetCode's n ≤ 300.
watch out
- Fill by length, not row by row:
dp[l][r]readsdp[l][k]anddp[k][r], which are shorter gaps. - “Last, not first” is the whole trick, and it's the same one behind matrix-chain multiplication, polygon triangulation (LC 1039) and merging stones (LC 1000).
- The interval shape in general:
dp[l][r]over a range, filled by length, with a split point in the middle.
practice
- 312Burst Balloons — this tab
- 1039Minimum Score Triangulation of Polygon
- 1000Minimum Cost to Merge Stones
- 516Longest Palindromic Subsequence — intervals, no split
- 664Strange Printer
Stock trading with a cooldown: DP over states
O(n) time · O(1) memoryLC 309: buy and sell one share as often as you like, but after a sale you must sit out a day. One number per day can't say where you are — you might own a share, have just sold one, or be free to buy. Three numbers can, one per state, and each day they move along fixed arrows.
the recipe
- state
- For each day, the best profit if you end it holding a share, having sold today, or resting with no share and free to buy.
- choice
- hold: keep the share, or buy today out of rest. sold: sell the share held yesterday. rest: stay out, or cool down after yesterday's sale.
- base
- Before day 0, rest = 0 and the other two are impossible: −∞.
- order
- Day by day, all three states from yesterday's values.
- answer
max(sold, rest)on the last day — ending with a share is never best.
why it works
Every legal sequence of trades is a walk through these three states, one step a day, and each state's best profit only depends on yesterday's three numbers. So the best over all walks can be carried forward a day at a time. The table is just the history of the three variables.
cost
Three numbers a day: O(n) time, and only yesterday's are needed, so O(1) memory.
watch out
- Compute all three from yesterday before assigning any. Updating
holdin place and then using it forsoldwould buy and sell on the same day. - Start the impossible states at −∞ —
INT_MIN / 2, so that adding a price can't overflow — not at 0. - The whole stock series is this pattern with other state machines: at most k trades adds the trade count to the state; a fee is subtracted on each sale.
practice
Best traveling route (Google onsite)
O(days × itineraries) time · O(days × places) memoryFrom a Google onsite question: you have N days of vacation and a list of itineraries, each [from, to, fun]. Every day you take one itinerary that starts where you are — on day 1, any itinerary at all — and collect its fun, which can be negative. If no itinerary starts where you are, the trip is over and the remaining days give 0. What is the most fun you can have? Greedy does badly on this map: one 9 leads to place 3 and the −3 loop (0 in all), the other to place 4, where the trip ends after one day (9). The best plan pays −4 to get out of 3 and collects 22. The fix is to decide from the end: how much can the last d days still bring, standing at each place?
ask before you code
- Must you travel every day, or may you stop? The post doesn't say, and with negative fun it changes the answer: 22 here if you must keep going, 24 if you may stop. The switch above runs either rule; the program prints both.
- May an itinerary be used twice? Nothing forbids it, and the DP assumes yes. If each one could be used only once, the past would matter (which ones are left), and the problem becomes a longest-trail search — NP-hard in general.
- How big is N? Up to 105 or so: the table below. Up to 109: the matrix trick at the end.
- The number, or the route too? The table gives both.
the recipe
- state
best[d][v]: the most fun from the last d days, standing at v.- choice
- Today's itinerary from v, then the best of the d − 1 days after it:
fun + best[d - 1][to]. If you may stop, stopping (0) is one more option. - base
best[0][v] = 0. A place with no itinerary stays 0: the trip is over.- order
- d = 1, 2, …, N. Each row only reads the row before it.
- answer
- Day 1 may start anywhere, so the largest
best[N][v]over the places that have an itinerary. Then walk forward, each day taking an itinerary that keeps the promise.
why it works
What the remaining days can bring depends only on where you stand and how many days are left — not on how you got there. Two different pasts that end at the same place with the same days left have the same best future, so best[d][v] is worked out once and shared. That is also why a −4 today is fine: best[d - 1][to] already knows it pays for itself.
cost
Each row looks at every itinerary once: O(N · E). Rows only read the row before, so two arrays hold the number; the full table here rebuilds the route. It is Bellman–Ford's round-by-round relaxation, maximizing instead of minimizing, for exactly N rounds — the same loop as LC 787, cheapest flights within k stops.
follow-up: N = 109
One day of the DP is a matrix product in which × becomes + and + becomes max. N days is MN, and squaring needs only log N products. The extra “trip over” place lets both rules use the same product.
watch out
- Under “keep going”, start each place's best at −∞, not 0. Otherwise a day with only negative options looks like a free day off.
- Day 1 is different from the rest: the answer is a max over starting places, and only over places that have an itinerary.
- N × the largest fun can pass 231: use
long long. - “Never take a negative itinerary” is also greedy, and also wrong here: the best trip takes the −4.
same shape
- 787Cheapest Flights Within K Stops — min instead of max
- 935Knight Dialer — count walks of length n
- 576Out of Boundary Paths
- 688Knight Probability in Chessboard
- 1575Count All Possible Routes
- 1928Minimum Cost to Reach Destination in Time
which shape when
| the problem says | state | like |
|---|---|---|
| Count or optimize steps toward n | dp[k] | climbing stairs |
| A row of things, each taken or not, neighbors interact | dp[i] | house robber |
| Reach a total, pieces reusable | dp[total] | coin change |
| Best subsequence of one array | dp[i], ending at i | LIS |
| Items and a budget, each item once | dp[i][budget] | knapsack |
| Two strings or two arrays | dp[i][j], prefixes | LCS, edit distance |
| A range that gets split or merged | dp[l][r], by length | burst balloons |
| A few modes that switch over time | dp[day][mode] | stock cooldown |
| Exactly k steps on a graph | dp[steps][node] | best route, LC 787 |
| Which items are used so far | dp[mask] | bitmask DP |
| A tree | dp[node][flag] | tree DP |
| A DAG | topological order | topo sort |
the recipe
- 1 · state
- The least information that decides a subproblem's answer. Count its values now: that count is the size of the table.
- 2 · choice
- The last decision, and the smaller state each option leaves. The recurrence takes the best (or the sum) over options.
- 3 · base
- The states small enough to answer directly — and a value for “impossible”.
- 4 · order
- Every state after the ones it reads: recursion with a memo, or loops over the table.
- 5 · cost
- States × work per state. Polynomially many states: polynomial time. 2n states: see P vs NP.
- words
- Overlapping subproblems: the same state is reached many ways. Optimal substructure: a best answer is built from best answers to the smaller states. Memoization is top-down; tabulation is bottom-up.