Dynamic Programming Problems

Eight classic interview problems — Climbing Stairs, House Robber (in a row and on a circle), Coin Change, Longest Increasing Subsequence, Word Break, Longest Common Subsequence, Edit Distance and Partition Equal Subset Sum — all solved with the same five-step recipe. For each one you will write the slow recursion first, see why it explodes, turn it into a table, watch that table fill cell by cell on your own input, and then shrink its memory. By the end you will be able to look at a new "how many ways / smallest / largest / is it possible" problem and write the table yourself.

The DP recipe: five steps that solve every problem on this page

The full theory — where the name comes from, why it works, and two longer case studies — is in C15 · Dynamic Programming. This page is the practical side: how to solve interview problems with it. A few words first, because every problem below uses them:

• A subproblem is a smaller version of the same question. "How many ways to climb 10 stairs?" has the subproblems "… 9 stairs?", "… 8 stairs?", and so on.
• Overlapping subproblems means the same small question is asked again and again by different branches of a plain recursion (a function that calls itself — see D07 · Recursion). That repetition is what makes plain recursion slow, and what DP removes.
• Optimal substructure means the best answer to the big question is built from best answers to smaller questions. The cheapest route to the top floor passes through some floor below it, and the part up to that floor must itself be the cheapest.
• The state is the small set of numbers that names one subproblem, like "i stairs" or "the first i letters of a and the first j letters of b". The table (usually a Dart List, sometimes a list of lists) holds one answer per state.
• The recurrence is the rule that computes one state's answer from smaller states. It always comes from listing the choices for the last move.
• Memoisation (top-down) keeps the recursion but writes each answer in a notebook (a Map) the first time. Tabulation (bottom-up) fills the table in a loop from the smallest state upwards, with no recursion at all.

How to recognise a DP problem

1. The question asks for a count ("how many ways…"), an optimum ("fewest", "cheapest", "longest", "most money") or a yes/no ("can you…", "is it possible…").
2. You make a sequence of choices (take or skip, step 1 or 2, which coin next, keep or drop a letter), and trying all of them would be exponential.
3. After a few choices you land in a situation you have seen before by a different route — the subproblems overlap.
4. The obvious greedy rule ("always grab the biggest") has a counterexample. When greedy is provably right, it is simpler — that is the subject of C16 · Greedy Algorithms and of the interval problems in Step 13.10 · Intervals & Greedy.
5. The input sizes fit a table: n up to a few thousand for an n² table, or a sum/amount up to about 10⁴ to 10⁶ for a table indexed by value.

The five-step recipe

1. Define the state in words. Write one sentence: "dp[i] = the fewest coins that make exactly i". If you cannot say it in words, you cannot fill it.
2. Write the recurrence from the choices. Ask "what was the last move?" and list every option. Combine them with + for counts, min/max for optimums, or for yes/no.
3. Set the base cases. The smallest states you can answer without the recurrence — usually "nothing yet": zero stairs, zero houses, the empty string, amount 0.
4. Choose the order of filling. Every state must be filled after the states it reads. Top-down memoisation finds the order for you through recursion; bottom-up tabulation needs you to pick it (usually small to large).
5. Optimise the space. Look at which cells the recurrence reads. If it only reads the last row or the last two cells, keep only those.

Warm-up: Unique Paths

The task. A robot stands in the top-left cell of a grid with rows rows and cols columns. Each move goes one cell right or one cell down. How many different paths reach the bottom-right cell?

Run the recipe on it, one step at a time:

1. State: dp[r][c] = the number of different paths from the start to cell (r, c).
2. Choices for the last move: the robot entered (r, c) either from the cell above, (r − 1, c), or from the cell to the left, (r, c − 1). A path cannot do both, so the two groups never overlap and we add them: dp[r][c] = dp[r − 1][c] + dp[r][c − 1].
3. Base cases: every cell of the top row and the left column has exactly 1 path — a straight line.
4. Order: row by row, left to right. Then "above" and "left" are always filled before they are read.
5. Space: a cell reads only the row above and the cell to its left, so one row of length cols is enough (the second function below).

The edge case: a single row. There is nothing to add — every cell is a base case.

1-D or 2-D table?

Count how many numbers you need to name one subproblem. One number (a position, an amount, a length) gives a 1-D list. Two numbers (a position in each of two strings, a row and a column) give a 2-D table, a list of lists in Dart. The table on the right of this chart is what each problem on this page uses:

The "+ 1" sizes come from a habit worth copying: let index 0 mean "nothing yet" (zero houses, the empty prefix). Then the base case lives in cell 0 and the loop never reads a negative index.

Climbing Stairs

The task. A staircase has n steps. From where you stand you may climb 1 step or 2 steps at a time. In how many different orders of moves can you reach the top step? (Order matters: 1 then 2 is different from 2 then 1.)

Brute force (plain recursion). The last move onto step n was a 1-step (from n − 1) or a 2-step (from n − 2). So ways(n) = ways(n − 1) + ways(n − 2), with ways(0) = ways(1) = 1. Correct — and terribly slow:

Why it explodes. ways(10) calls ways(9) and ways(8); ways(9) calls ways(8) again, and so on. The number of calls almost doubles with every extra step:

The call count is 2 × F(n + 1) − 1, where F is the Fibonacci sequence 1, 1, 2, 3, 5, … — it grows like 1.618ⁿ. Growth rates are explained in C03 · Growth of Functions.

Top-down fix (memoisation). Keep the recursion, add a notebook. The first time ways(k) is solved, store it; every later call reads it in O(1). Now each k from 2 to n is solved once: O(n) time, plus O(n) for the notebook and the recursion stack.

Bottom-up (the table). State: dp[i] = ways to stand on step i. Recurrence: dp[i] = dp[i − 1] + dp[i − 2]. Base: dp[0] = 1 (standing still at the bottom is one way — the empty sequence of moves) and dp[1] = 1. Order: i = 2, 3, …, n.

The edge case n = 1 never reaches the table at all: the first line answers it.

Complexity. Table: time O(n), space O(n). Two variables: time O(n), space O(1), because dp[i] reads only the two cells just before it.

Follow-ups interviewers ask. Each step has a toll and you want the cheapest climb (p11-q3). Hops of 1, 2 or 3 (p11-q4). Tiling a 2 × n board with dominoes is the same recurrence in disguise (p11-q6). Some steps are broken — set their dp to 0 and keep going.

The idea underneath: the recursion tree and its repeated calls — D07 · Recursion — and the "elements of DP" in C15 · Elements of dynamic programming.

House Robber (a street, then a circle)

The task. Houses stand in a row; nums[i] is the money in house i. A burglar alarm rings if two neighbouring houses are robbed on the same night. What is the most money you can collect without ringing it?

Brute force. At house i, either rob it (and jump to i + 2) or skip it (go to i + 1). Two branches per house: O(2ⁿ), and the same "best from house k onwards" is recomputed many times.

The recipe. State: dp[i] = the most money from the first i houses (houses 0 to i − 1). Choices for house i − 1: skip it → dp[i − 1]; rob it → dp[i − 2] + nums[i − 1]. So dp[i] = max(dp[i − 1], dp[i − 2] + nums[i − 1]). Base: dp[0] = 0, dp[1] = nums[0]. Order: left to right. Space: only the last two values are read.

Complexity. Time O(n). Space O(n) for the table, O(1) for the two-variable version.

House Robber II: the houses stand in a circle

Now the street is a ring, so the first and last houses are neighbours too. The whole difference is one rule: house 0 and house n − 1 can never both be robbed. So at least one of them is left alone — and that splits the problem into two straight streets we can already solve: one without the last house, one without the first. The answer is the better of the two.

Follow-ups interviewers ask. Return which houses were robbed (walk back through the table: if dp[i] = dp[i − 1] house i − 1 was skipped, otherwise robbed — the animation does this at the end). Houses on a binary tree, where a parent and child are neighbours (keep two numbers per node: best with and without it). Delete-and-earn: picking value v deletes all v − 1 and v + 1, which becomes house robber over the values.

The idea underneath: "take it or leave it" choices, the heart of C15 · Classic interview DP.

Coin Change (and why greedy fails)

The task. You have unlimited coins of each value in coins. Find the fewest coins that add up to exactly amount, or −1 if no combination works.

Brute force. Try every coin as the last coin and recurse on what is left. The same remaining amount is reached by many routes (5 then 1 leaves the same rest as 1 then 5), so the work is exponential.

Adding a notebook gives the top-down version — each amount is solved once:

The recipe. State: dp[a] = the fewest coins that make exactly a. Choices: the last coin is some c ≤ a, leaving a − c. So dp[a] = 1 + min over coins c ≤ a of dp[a − c]. Base: dp[0] = 0; every other cell starts at ∞ ("cannot be made yet"). Order: a = 1, 2, …, amount — every a − c is smaller than a, so it is already final.

The finished table for Example 1, coins [1, 5, 6, 9] and amount 11:

The edge case: an amount no combination can make. The ∞ in the last cell survives the whole loop.

Why "biggest coin first" is wrong

The greedy rule — keep handing over the biggest coin that still fits — works for everyday coin systems like 1, 2, 5, 10, 20, 50. It fails for others. With coins 1, 3, 4 and amount 6, greedy takes 4, then 1, then 1 (three coins), but 3 + 3 uses two. Greedy commits to the 4 and can never take it back; the table keeps every option open until the end. Greedy can even get stuck with coins 3 and 5 and amount 9: it takes 5, then 3, and 1 is left over, although 3 + 3 + 3 works. The proof-level story is in C16 · Coin changing.

Complexity. Time O(amount · k) for k coin values; space O(amount). There is no further space saving: dp[a] can read a cell as far back as the largest coin.

Follow-ups interviewers ask. Count the number of ways to make the amount, where 1 + 2 and 2 + 1 are the same way (p11-q9 — the loop order matters). Fewest perfect squares adding to n (p11-q22 — coin change with square coins). Each coin may be used at most once (that is 0/1 knapsack — see Partition below). Print the coins used (keep the coin that won each cell, as the animation does).

The idea underneath: unbounded choices over a value-indexed table; compare with the 0/1 knapsack in C16 · Fractional vs 0/1 knapsack.

Longest Increasing Subsequence

The task. A subsequence is what is left after deleting some numbers from a list without changing the order of the rest (the kept numbers need not be next to each other). Return the length of the longest subsequence whose numbers strictly increase.

Brute force. For each number, take it (if it is bigger than the last one taken) or skip it: 2ⁿ subsequences.

The recipe. The trick is the state: "the longest run in the first i numbers" is hard to extend, because you do not know what that run ends with. So pin down the end. State: dp[i] = the length of the longest increasing subsequence that ends at index i. Choices: the number before nums[i] in that run is some earlier nums[j] < nums[i], or there is none. So dp[i] = 1 + max(dp[j]) over those j, or 1. Base: every dp[i] starts at 1 (the number alone). The answer is the largest dp[i], not dp[n − 1].

The O(n log n) version: patience piles

Deal the numbers like cards into piles from left to right; each card goes on the leftmost pile whose top is ≥ the card, or starts a new pile on the right. The number of piles is the answer. In code, keep only the pile tops in a list tails: tails[k] = the smallest last number of any increasing subsequence of length k + 1 seen so far. Small ends are good — they leave more room for later numbers to extend the run. tails is always sorted, so each new number finds its place by binary search (Step 13.5 · Binary Search): if it is bigger than every tail it makes the longest run one longer; otherwise it replaces the first tail that is ≥ it.

Complexity. Table version: time O(n²) (every pair j < i), space O(n). Patience version: time O(n log n) (one binary search per number), space O(n). The table has no easy space saving, because dp[i] reads every earlier cell.

Follow-ups interviewers ask. Print one longest subsequence (remember, for each i, which j it extended — the animation does this). Count how many longest subsequences there are (keep a count next to each dp[i]). Nesting picture frames or envelopes by width and height (p11-q26 — sort, then LIS on the heights).

The idea underneath: choosing a state that makes the recurrence possible, discussed in C15 · Elements of dynamic programming; binary search on a sorted list in Step 13.5 · Binary Search.

Word Break

The task. Given a string s with no spaces and a list of dictionary words, answer true if spaces can be inserted into s so that every piece is a dictionary word. A word may be used any number of times.

Brute force. Peel any dictionary word off the front and solve the rest. The same leftover suffix is reached through different first words, so the work can be exponential.

The recipe. State: dp[i] = true when the first i letters s[0 .. i) can be cut into words (the notation s[j .. i) means letters j up to but not including i, exactly what Dart's s.substring(j, i) returns). Choices: the last word is s[j .. i) for some cut point j. So dp[i] = true if some j has dp[j] true and s[j .. i) in the dictionary. Base: dp[0] = true. Order: i = 1 … n. Put the words in a Set first so each lookup is O(1) on average.

Complexity. Time O(n²) cut checks, each building a substring of up to n letters, so O(n³) character work in the worst case; if no word is longer than L letters, only try j ≥ i − L and it drops to O(n · L²). Space O(n) for the table plus the dictionary set.

Follow-ups interviewers ask. Return every possible sentence, not just yes/no (p11-q25 — memoise the list of sentences per start index). Count the sentences. Use a trie (a letter tree) to walk forward from each cut point instead of building substrings — the subject of Step 13.8 · Tries & Heaps.

The idea underneath: a prefix table over a string; string slicing costs are in D24 · Slice, clean, replace and split.

Longest Common Subsequence

The task. Given two words a and b, return the length of the longest sequence of letters that is a subsequence of both (same order, gaps allowed).

Brute force. Compare first letters: equal → keep both and move on; different → drop the first letter of a, or of b, and take the better. Two branches per mismatch: up to 2^{m + n} calls, with the same pair of suffixes solved over and over.

The recipe. Two words, so the state needs two numbers. State: dp[i][j] = the LCS length of the first i letters of a and the first j letters of b. Choices on the last letters a[i − 1] and b[j − 1]: equal → dp[i − 1][j − 1] + 1 (diagonal); different → max(dp[i − 1][j], dp[i][j − 1]) (above or left). Base: row 0 and column 0 are 0 (an empty prefix has nothing in common). Order: row by row, left to right. In the animation, the column marked ∅ means "no letters of b yet" and the row marked ∅ means "no letters of a yet".

Complexity. Time O(m · n), space O(m · n) for the table. Space optimisation: row i reads only row i − 1, so two rows of length n + 1 are enough — O(n) — but then you can no longer walk back to print the letters (p11-q32).

Follow-ups interviewers ask. Print one LCS (p11-q21). Longest common substring (p11-q20). Shortest word that contains both as subsequences: |a| + |b| − LCS. Fewest deletions to make two words equal: |a| + |b| − 2 · LCS. Longest palindromic subsequence: the LCS of a word and its reverse (p11-q29).

The idea underneath: a 2-D table over two prefixes, built step by step in C15 · Longest common subsequence.

Edit Distance

The task. Turn word a into word b using three kinds of edit, each costing 1: insert a letter, delete a letter, or replace a letter with another. Return the fewest edits needed.

Brute force. The same three choices, as recursion from the front: up to three calls per mismatch, exponential.

The recipe. State: dp[i][j] = the fewest edits turning the first i letters of a into the first j letters of b. Choices on a[i − 1] and b[j − 1]: equal → dp[i − 1][j − 1] for free; otherwise 1 + the smallest of delete dp[i − 1][j] (above), insert dp[i][j − 1] (left), replace dp[i − 1][j − 1] (diagonal). Base: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything). Order: row by row.

Complexity. Time O(m · n), space O(m · n); with two rows (the second function) space is O(n). Swap the words first so the shorter one indexes the columns, and the rows are as short as possible.

Follow-ups interviewers ask. Print the edits (walk back from the corner, as the animation does at the end). Only insert and delete allowed: m + n − 2 · LCS. "One edit away?" in O(n) without a table — walk both words with two pointers. Different costs per edit — the same table with weighted choices.

The idea underneath: the same two-prefix table as LCS with three choices instead of two — see C15 · Classic interview DP.

Partition Equal Subset Sum

The task. Given a list of positive whole numbers, can you split them into two piles with equal sums? Every number goes into exactly one pile.

Brute force. Put each number on the left or the right pile: 2ⁿ ways.

The recipe. First the shortcut: if the total is odd, answer false. Otherwise the question is "can some numbers add up to target = total ÷ 2?" — a 0/1 knapsack (each item taken at most once) on sums. State: can[s] = true when some of the numbers seen so far add up to exactly s. Choices for a new number x: leave it out (can[s] stays) or put it in (can[s − x] from before x). Base: can[0] = true. Order: numbers one by one; for each number, sums from target down to x.

Why backwards? A 2-D table can[k][s] ("using the first k numbers") would read row k − 1 when filling row k. We keep one row and overwrite it in place. Walking down, when we read can[s − x] it is a smaller sum that has not been visited yet in this round — still the old row's value, from before x. Walking up, can[s − x] may have been ticked a moment ago by this same x, so x gets used twice. The third animation below shows exactly that going wrong.

The same input, filled forwards — the classic bug. Watch the single 1 get used three times:

Complexity. Time O(n · target), space O(target) — the space optimisation from a 2-D (n + 1) × (target + 1) table to one row is exactly what the backwards loop makes safe. This is called pseudo-polynomial: fast when the numbers are small, slow when they are huge (a target of 10¹² would need 10¹² boxes).

Follow-ups interviewers ask. Count the ways to give each number a + or − sign so the total is a target (p11-q17). Split into k equal groups (p11-q33 — bitmask DP). Smallest possible difference between the two piles (the largest ticked box ≤ half). Classic 0/1 knapsack with weights and values: the same backwards loop with max instead of or.

The idea underneath: 0/1 knapsack and why it is not greedy — C16 · Fractional vs 0/1 knapsack; the bit tricks for the k-group version in D03 · Numbers & Bits.

Quiz

Interview questions

Variations and follow-ups of the problems above — the questions interviewers move to once the classic version is solved. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow recursive or try-everything reference.

Cheat sheet

Loop direction rule: a 1-D table filled from small to large lets an item be used again in the same round (unlimited copies, as in coin change); filling from large to small uses each item at most once (0/1 knapsack, as in partition).