Dynamic Programming: The Core Idea

Dynamic programming is the pattern for a best value or a count over a series of choices, where the same smaller question keeps coming back. "What is the most money you can take?" "How many ways can you climb the stairs?" "What is the fewest number of coins?"

The name is unhelpful — it comes from 1950s planning research and says nothing about the method. Read it as recursion with a notebook. You write the obvious recursive solution, notice it answers the same small question many times, and write each answer down the first time so the second time is a lookup.

How to recognise it

Signal 1 — a best value or a count. "Maximum", "minimum", "longest", "fewest", "how many ways", "is it possible". The question wants one number, not a list of every answer. (Every answer would be backtracking.)

Signal 2 — a series of choices. At each step you take an item or leave it, climb one stair or two, match a character or skip it. The answer depends on the whole series.

Signal 3 — medium constraints. n up to about 10⁴ with a two-index state, or up to 10⁵–10⁶ with a one-index state. Too big for trying every series (2ⁿ), not obviously sorted or greedy.

Signal 4 — greedy has a counter-example. With coins 1, 3 and 4 and amount 6, "take the biggest coin" gives 4 + 1 + 1, three coins. The best is 3 + 3, two coins. When the locally best step can lose, greedy is out and DP is usually in.

The signals are hints. Here is a test that is close to decisive: write the brute-force recursion and look for repeated calls. If the same call appears more than once, caching it is dynamic programming. If every call is different, a cache buys nothing and you are in backtracking or divide-and-conquer territory.

The two properties

Dynamic programming needs two things to be true. Both show up in one small example.

Climbing Stairs. You climb a staircase of n steps, taking 1 or 2 steps at a time. How many different orders of steps reach the top? Your last move came either from step n − 1 or from step n − 2, and those two groups never overlap. So:

ways(n) = ways(n - 1) + ways(n - 2),   ways(0) = ways(1) = 1

That is the Fibonacci rule. Now count the calls the plain recursion makes for ways(5) (the diagram writes it as f):

Property 1 — overlapping subproblems. The same smaller question is asked many times. ways(3) is solved twice, and each time it solves ways(2) and ways(1) again underneath. The waste grows fast: the call count for ways(n) is 2 × fib(n + 1) − 1. For n = 40 that is 331,160,281 calls to learn 41 numbers. Measured in Python on a laptop, n = 32 takes 0.25 seconds, so n = 40 takes about 25 seconds. A notebook makes it 41 steps.

Merge sort is a useful contrast. It also splits a problem into smaller ones, but the left half and the right half are different pieces — no piece is ever solved twice — so a cache would do nothing. That is divide and conquer, not DP.

Property 2 — optimal substructure. The best answer to the whole is built from the best answers to parts. The fewest coins for 6 uses the fewest coins for 6 − c for some coin c; you never need a worse way to make 3 in order to make 6 as well as possible. This is what lets you keep one number per state and throw the rest away.

Where it fails: "the longest path between two nodes that never repeats a node". The longest A-to-C path is not the longest A-to-B path plus the longest B-to-C path, because those two might share nodes. No optimal substructure, so no DP — and that problem has no known fast solution. Ask both questions out loud before you commit: does the same subproblem come back? and can the best whole be built from best parts?

From recursion to a table: four stages

Every DP solution can be written four ways. They are the same solution; only where the answers are stored changes. Carry Climbing Stairs through all four.

Stage 1 — plain recursion. Write the rule straight into code.

1def climb_rec(n: int) -> int:2    """Ways to climb n stairs with steps of 1 or 2: plain recursion."""3    if n <= 1:4        return 1                     # 0 or 1 stairs: exactly one way5    return climb_rec(n - 1) + climb_rec(n - 2)

O(2ⁿ) time (more precisely about 1.6ⁿ), O(n) stack. Never ship this; use it to find the rule.

Stage 2 — memoisation (top-down). Add a dictionary. Look up before computing; store after.

1def climb_memo(n: int) -> int:2    """Same recursion; each answer is stored the first time it is computed."""3    memo: dict[int, int] = {}45    def ways(i: int) -> int:6        if i <= 1:7            return 18        if i in memo:9            return memo[i]            # solved before: no recursion10        memo[i] = ways(i - 1) + ways(i - 2)11        return memo[i]1213    return ways(n)

The rule, the base case and the shape are unchanged — three lines were added. Each of the n states is computed once: O(n) time, O(n) memo plus O(n) stack. For n = 40, calls drop from 331 million to 79. In Python, @functools.cache on the plain recursion does the same in one line; use it to move fast, and be ready to write the dictionary if asked what it does.

Stage 3 — tabulation (bottom-up). Start from the base cases and fill upward. The recursion disappears.

1def climb_table(n: int) -> int:2    """Fill dp[0..n] from the base cases upward."""3    dp = [0] * (n + 1)4    dp[0] = 15    if n >= 1:6        dp[1] = 17    for i in range(2, n + 1):8        dp[i] = dp[i - 1] + dp[i - 2]     # the same rule, read left to right9    return dp[n]

For n = 6 the table fills as dp = [1, 1, 2, 3, 5, 8, 13]: 13 ways. Check the small ones by hand — 2 stairs: 1+1 or 2; 3 stairs: 1+1+1, 1+2, 2+1. O(n) time, O(n) space, no recursion limit.

Stage 4 — space optimisation. dp[i] reads only dp[i - 1] and dp[i - 2]. Nothing older is read again, so keep two variables.

1def climb(n: int) -> int:2    """Only the last two entries are ever read, so keep two variables."""3    prev2, prev1 = 1, 1              # dp[i-2], dp[i-1], starting at dp[0], dp[1]4    for _ in range(2, n + 1):5        prev2, prev1 = prev1, prev1 + prev26    return prev1

In an interview, say the recursion out loud, then write memoisation or tabulation, and offer the space saving last. Presenting the two-variable loop first hides the rule and is hard to explain.

Defining the state and the transition

The four stages are mechanical. The hard part is the rule itself, and the rule depends on one choice: what is a state? Use these five steps, in this order, every time.

1. State — finish the sentence "dp[...] is the [best value / number of ways] for [which smaller problem]". If you cannot finish it, stop; no code will work.
2. Transition — list the choices at one state and combine them: max or min for a best value, + for a count, or for "is it possible".
3. Base cases — the smallest states whose answers you know: usually the empty prefix, with 0, 1, True or infinity.
4. Order — fill each state after every state it reads. For prefixes, left to right; for grids, row by row.
5. Answer and space — say which cell holds the answer, then keep only the rows the transition reads.

How to find a good state: ask "what do I need to know about the choices made so far to make the rest of them well?" Keep that, and nothing more.

• In Climbing Stairs, only which step you stand on matters, not how you got there. State: one index.
• In House Robber, only how many houses you have passed, because the rule looks at the last one or two. State: one index.
• In Edit Distance you are eating two strings at once, so you need how far into each. State: two indices.
• In 0/1 knapsack you also need how much room is left. State: item index and remaining capacity.
• In Longest Increasing Subsequence you need the last value taken, because the next one must be bigger. State: "the subsequence ending at index i".

If you are writing the transition and find you need a fact the state does not hold — "but was the last item taken?" — the state is too thin. Add that fact as another index.

The shapes it takes

The problem lessons that follow take one or two of each shape, from easiest to hardest.

Complexity

The cost of almost every DP solution is:

time  = (number of distinct states) × (work to compute one state)space = (number of distinct states), before any space saving

Climbing Stairs: n states × O(1) = O(n). Coin Change: amount states × one check per coin = O(amount × coins). Edit Distance: m × n states × O(1) = O(m × n). Longest Increasing Subsequence in its simple form: n states × a scan of up to n earlier ones = O(n²). Learn this formula — it gives you the complexity before you have written a line.

Where it goes wrong

1. A state that is too thin. "The longest increasing subsequence within the first i numbers" cannot be extended, because it does not say what value it ends on. Fix: add what is missing, or redefine the state as "ending at i".
2. Wrong base cases. Coin Change needs dp[0] = 0 and infinity everywhere else. Start the others at 0 and every amount "costs" 0 coins. Word-break style problems need dp[0] = True, or nothing ever becomes True. Check by computing the first real state by hand.
3. An order that reads cells not yet filled. A grid rule that reads dp[r - 1][c] and dp[r][c - 1] needs rows top to bottom and columns left to right. Reverse either and you read zeros.
4. Space saving in the wrong direction. When a 2-D table is squeezed into one row, the loop direction decides whether you read the old row or the new one. For 0/1 knapsack a forward loop lets one item be used twice. Confirm the full table first, then squeeze.