Dynamic programming

Dynamic programming for coding interviews, from recursion to memoization to a table. A four-step recipe, step-throughs of house robber and longest common subsequence, code in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Senior16 min read

Read first: Backtracking

Dynamic programming has a reputation for being the hardest pattern, mostly because it’s taught backwards: here’s a table, here’s the formula that fills it. Nobody finds a table first. You find a recursive answer first, notice it solves the same small problems over and over, and then remember those answers instead of recomputing them. The table is just the last, tidiest form of that memory.

DP applies when a problem has two properties. The first is optimal substructure: the best answer is built from best answers to smaller versions of the same problem. The second is overlapping subproblems: the recursion asks for the same smaller answers many times. Backtracking explores every path. DP notices that many paths lead to the same place, and solves each place once.

How to spot it

“How many ways”, “minimum cost”, “maximum value”, “longest”, “can you reach”, where each step is a choice, and choices made earlier change what’s possible later.
A greedy idea that almost works. Take coin change with coins [1, 3, 4] and amount 6. Greedy takes 4 + 1 + 1, three coins. But 3 + 3 is two. When greedy fails on a small example, think DP.
Two strings compared character by character: longest common subsequence, edit distance, interleaving.
A brute-force recursion with repeated calls. Draw the first few levels of the call tree. If the same arguments appear twice, memoize.

If the problem wants every solution listed, that’s backtracking. DP counts or optimizes them, without building each one.

Watch it run

House robber first: rob houses for the most money, never two next to each other. The state best[i] is “the most money from houses 0 to i”. At each house there are two choices, skip it or rob it, and each choice reads an answer that’s already in the table.

houses

207192331445

best

best[i] = most money from houses 0..i
best[0] = houses[0]; best[1] = max(houses[0], houses[1])
for i in range(2, len(houses)):
best[i] = max(best[i - 1], # skip it
best[i - 2] + houses[i]) # rob it

Rob houses for the most money, never two next to each other. The state: the best total using houses 0 to i.

1 / 8

Then switch to 2D: common subsequence. Each cell is the answer for a prefix of each string. A match extends the diagonal. A mismatch takes the better of two options: drop a letter from one string (above), or from the other (left). The table fills row by row, so the three cells it reads are always done.

The recipe, worked through

Take coin change: the fewest coins that make an amount.

State, in words: fewest[a] = the fewest coins that make exactly a. If you can’t say the state in one sentence, you don’t have it yet.
Recurrence: the last coin used is some coin c, and the rest makes a - c in the fewest coins. So fewest[a] = 1 + min(fewest[a - c]) over coins with c <= a.
Base cases: fewest[0] = 0. Amounts no combination can reach stay at a sentinel such as amount + 1, which no real answer can equal.
Order: each amount reads smaller amounts, so fill from 1 up to amount.

That’s O(amount × coins) time and O(amount) memory. Before the table, it was a recursion that recomputed fewest(5) from every path that reached 5, which is exponential.

The template

House robber with two variables, coin change with a 1D table, and longest common subsequence with a 2D table:

DynamicProgramming.javaexample.pyDynamicProgramming.csmain.goexample.ts

import java.util.Arrays;

public class DynamicProgramming {
    static int rob(int[] houses) {
        // State: best[i] = most money from houses 0..i. Recurrence: skip house i and keep
        // best[i-1], or rob it and add it to best[i-2]. Each step reads only the last two
        // states, so two variables replace the table: O(n) time, O(1) memory.
        int twoBack = 0, oneBack = 0; // best two houses back, best one house back
        for (int money : houses) {
            int bestHere = Math.max(oneBack, twoBack + money);
            twoBack = oneBack;
            oneBack = bestHere;
        }
        return oneBack;
    }

    static int coinChange(int[] coins, int amount) {
        // State: fewest[subAmount] = fewest coins that make subAmount. Recurrence: try each
        // coin as the last one, so fewest[subAmount] = 1 + min(fewest[subAmount - coin]). Fill
        // small amounts first, so every subAmount - coin is final when read. impossible marks
        // amounts no combination can make; amount + 1 instead of MAX_VALUE so the + 1 below
        // can't overflow.
        int impossible = amount + 1;
        int[] fewest = new int[amount + 1];
        Arrays.fill(fewest, impossible);
        fewest[0] = 0;
        for (int subAmount = 1; subAmount <= amount; subAmount++) {
            for (int coin : coins) {
                if (coin <= subAmount) {
                    fewest[subAmount] = Math.min(fewest[subAmount], fewest[subAmount - coin] + 1);
                }
            }
        }
        return fewest[amount] == impossible ? -1 : fewest[amount];
    }

    static int longestCommonSubsequence(String text1, String text2) {
        // State: commonLength[i][j] = longest common subsequence of the first i letters of
        // text1 and first j of text2, with an extra row and column of 0 for the empty prefix
        // so the edges need no special case. Matching letters extend the diagonal; otherwise
        // drop a letter from one side, keep the better.
        int[][] commonLength = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                commonLength[i][j] = text1.charAt(i - 1) == text2.charAt(j - 1)
                        ? commonLength[i - 1][j - 1] + 1
                        : Math.max(commonLength[i - 1][j], commonLength[i][j - 1]);
            }
        }
        return commonLength[text1.length()][text2.length()];
    }

    public static void main(String[] args) {
        check(rob(new int[] {2, 7, 9, 3, 1, 4}) == 15);
        check(rob(new int[0]) == 0);
        check(coinChange(new int[] {1, 2, 5}, 11) == 3);
        check(coinChange(new int[] {2}, 3) == -1);
        check(coinChange(new int[] {1, 3, 4}, 6) == 2); // greedy takes 4 + 1 + 1; DP finds 3 + 3
        check(longestCommonSubsequence("ace", "abcde") == 3);
        check(longestCommonSubsequence("abc", "def") == 0);
        System.out.println("ok: rob, coinChange and longestCommonSubsequence");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Top-down, in Python

Write the recurrence as a function, and let a cache remember each answer. It reads exactly like the recipe and is often the fastest way to a correct solution in an interview:

from functools import cache

def coin_change(coins: list[int], amount: int) -> int:
    @cache
    def fewest(a: int) -> float:
        if a == 0:
            return 0
        return min((fewest(a - c) + 1 for c in coins if c <= a), default=float("inf"))

    best = fewest(amount)
    return -1 if best == float("inf") else int(best)

The catch is depth. fewest(10_000) recurses about 10,000 deep, past Python’s default limit of 1,000. Converting to bottom-up removes the recursion entirely, which is the usual follow-up.

The common shapes

1D line: climbing stairs, house robber, decode ways, longest increasing subsequence. State: the best answer ending at, or using up to, index i.
Two strings, 2D grid: LCS, edit distance, distinct subsequences. State: the answer for the first i letters of one and the first j of the other. Add a row and column for the empty prefix.
Grid paths: unique paths, minimum path sum. State: the answer at cell (r, c), read from above and the left.
Knapsack: partition equal subset sum, target sum, coin change. The state is items considered × capacity. For 0/1 knapsack in one row, loop the capacity downward, so each item is used at most once. Loop it upward when items can repeat, as in coin change.

Complexity

Count the states, and the work per state. Coin change has amount states, with len(coins) work each. LCS has m × n states, O(1) each. Longest increasing subsequence has n states, O(n) each, for O(n²). An O(n log n) version exists, using binary search over the smallest tail of each length.

Say this out loud

Let fewest of a be the fewest coins that make a. The last coin is some c, so fewest of a is one plus the minimum of fewest of a minus c. Base case fewest of 0 is 0, and I fill amounts in increasing order. That’s O(amount × coins).

Interview questions

Interviewer asksHow do you know a problem is DP and not greedy?

Try to break the greedy choice with a small example. Can taking the locally best option ever block a better total? Then greedy is wrong. Is the remaining problem, after any choice, a smaller copy of the original? Then DP fits. Coin change with [1, 3, 4] and 6 breaks greedy. With US coins, greedy happens to work. That’s exactly why an interviewer will pick other coins.

Interviewer asksReduce LCS from O(m × n) memory to O(n).

Each row only reads the row above it and the cell to its left. Keep two rows, previous_row and current_row, and swap them after each row. With care you can use one row and a variable holding the old diagonal value, which you save before overwriting the cell. Reconstructing the subsequence itself still needs the full table, or a divide-and-conquer method (Hirschberg’s algorithm).

Interviewer asksPartition equal subset sum: why does the capacity loop go backward?

The one-row table can[s] means “some subset of the items seen so far sums to s”. Looping s downward means can[s - x] still holds the value from before item x was considered, so x is used at most once. Looping upward would read a value that already used x, letting it be used again, which is the unbounded knapsack instead.

Practice

10 problems on LeetCode: 2 easy, 8 medium

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

Use it when the question asks how many, the minimum, the maximum or whether it’s possible, and the recursion repeats subproblems.
The recipe: state in words, recurrence, base cases, fill order.
Top-down = recursion plus a cache. Bottom-up = table in order, no recursion, and memory can shrink to the rows you still read.
Cost: states × work per state.
Shapes to recognize: 1D line, two-string grid, grid paths, knapsack (down for 0/1, up for unbounded).