Dynamic programming

1 · Why DP matters: the intuition

Dynamic programming is the discipline of not solving the same subproblem twice. Two properties together unlock it. Overlapping subproblems: the naive recursion keeps revisiting the same inputs. Optimal substructure: the optimal answer at a bigger size is built from optimal answers at smaller sizes. When both hold, caching turns an exponential into a polynomial.

Memoisation and tabulation are dual sides of the same coin. Memoisation is "write the recursion, slap a cache on it." Tabulation is "fill the table in dependency order, no recursion at all." They produce the same answer with the same big-O; pick whichever is easier to reason about for the problem in hand. Memoisation reads more like the original recurrence; tabulation gives you tight control over space and order.

DP shows up in roughly 30% of senior-level interview problems for a reason. It is one of the few patterns that separates candidates who can model a problem from those who can only solve a pre-modelled one. Getting the state right is the hard part; once the state is right, the recurrence usually falls out, and the code is almost mechanical.

2 · How to recognise it

DP is usually the right pattern when several of the following hold. The first two are the strongest signals. The five shapes that follow cover almost every LeetCode DP question. Match the prompt to a shape before writing code.

• "Count the number of ways to..." Counting problems map cleanly to DP because the count for a state is the sum of counts of the states it transitions from. LC 70 Climbing Stairs (count ways to reach step n), LC 91 Decode Ways (count valid decodings of a digit string).
• "Minimise / maximise something over choices." Optimisation framing. At each step, pick the best of a few options; remember the best across all suffixes. LC 322 Coin Change (minimise coins), LC 198 House Robber (maximise loot under no-adjacent constraint).
• "Is it possible to..." / "Does there exist a..." Boolean reachability. State holds "can I reach this configuration with these resources?" LC 416 Partition Equal Subset Sum (can this set split evenly?), LC 139 Word Break (can this string be tokenised?).
• "Longest / shortest subsequence" of a string or array. Classic two-pointer DP over prefixes. LC 300 LIS (longest increasing), LC 1143 LCS (longest common subsequence), LC 72 Edit Distance (shortest edit script). The state is usually dp[i][j] over prefixes of two inputs.
• 2D grid with directional moves. Paths from top-left to bottom-right with only down/right moves. LC 62 Unique Paths (count paths), LC 64 Min Path Sum (minimise sum), LC 174 Dungeon Game (work backward from goal). The grid IS the DP table.
• Overlapping subproblems. The naive recursion calls itself on the same arguments many times. Fibonacci is the textbook example; coin change and LCS are the realistic ones.
• Brute force is exponential but the distinct subproblem count is polynomial. If you can enumerate a small state space (n, or n × m, or n × W) but the naive recursion is 2ⁿ, that gap is exactly what memoisation closes.

3 · Sister algorithms

DP is one corner of a triangle with memoisation, tabulation, and several variants. Knowing the boundaries saves you from over-engineering a problem that wanted something simpler.

4 · Canonical example: Coin Change (LC 322)

Problem. Given an array of coin denominations and a target amount, return the fewest number of coins that sum to amount. Return -1 if it's impossible. Assume an unlimited supply of each coin.

Input:  coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1.

Input:  coins = [2], amount = 3
Output: -1

The state is the remaining amount. The transition: for each coin, if it fits, the best answer at this amount is 1 + dp[amount - coin]. Take the minimum across coins. Base case: dp[0] = 0 (zero coins make zero). Anything unreachable stays at infinity and returns -1 at the end.

5 · Reference implementation

Two versions of the same recurrence (top-down and bottom-up) in Go and Python. Top-down reads like the recursion you wrote on the whiteboard; bottom-up is usually faster and avoids stack depth issues. Pick whichever is easier to reason about, then convert if needed.

Go: bottom-up, the interview default

func coinChange(coins []int, amount int) int {
    const INF = 1 << 30
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = INF
    }
    dp[0] = 0                       // base case: 0 coins make amount 0

    for a := 1; a <= amount; a++ {
        for _, c := range coins {
            if c <= a && dp[a-c]+1 < dp[a] {
                dp[a] = dp[a-c] + 1
            }
        }
    }

    if dp[amount] == INF {
        return -1
    }
    return dp[amount]
}

Go: top-down with memoisation

func coinChangeTopDown(coins []int, amount int) int {
    memo := make(map[int]int)
    const INF = 1 << 30

    var best func(remaining int) int
    best = func(remaining int) int {
        if remaining == 0 {
            return 0
        }
        if remaining < 0 {
            return INF
        }
        if v, ok := memo[remaining]; ok {
            return v
        }
        m := INF
        for _, c := range coins {
            sub := best(remaining - c)
            if sub+1 < m {
                m = sub + 1
            }
        }
        memo[remaining] = m
        return m
    }

    result := best(amount)
    if result == INF {
        return -1
    }
    return result
}

Python: for reference

# Top-down — memoised recursion
from functools import lru_cache

def coin_change_topdown(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def best(remaining: int) -> int:
        if remaining == 0: return 0
        if remaining < 0:  return float('inf')
        return min(1 + best(remaining - c) for c in coins)

    result = best(amount)
    return result if result != float('inf') else -1

# Bottom-up — tabulation
def coin_change(coins: list[int], amount: int) -> int:
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0                                # base case: 0 coins make amount 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1

    return dp[amount] if dp[amount] != INF else -1

6 · Variations

The shape of the state and how you iterate changes by problem type. Seven common variations:

7 · From exponential recursion to linear table

DP earns its keep because the naive recursion revisits the same subproblems. For Coin Change with coins [1, 2, 5] and amount 5, the bare recursion explores this tree:

The orange nodes are duplicates: states that have been computed elsewhere in the tree. Memoisation caches each result the first time it's computed, turning every duplicate into an O(1) cache hit. Tabulation flips the direction: instead of "compute on demand and cache," fill a table bottom-up so every state is computed exactly once.

8 · The six DP archetypes

Once you've solved fifty DP problems, you notice they all reduce to roughly six shapes. Recognising which archetype a new problem fits cuts the time-to-solution dramatically. The state and transition fall out of the archetype rather than having to be derived from scratch.

9 · Space optimisation: rolling arrays

Many DP solutions only access the previous one or two rows of the table. Keeping the whole table around is wasteful. You can roll the storage down to two rows (or one, in the cleverest cases) for the same answer at a fraction of the space.

# Edit Distance — full O(m × n) table
def edit_distance_full(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

# Same problem, O(min(m, n)) space — only the previous row matters
def edit_distance_rolling(s1: str, s2: str) -> int:
    if len(s1) < len(s2): s1, s2 = s2, s1
    m, n = len(s1), len(s2)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1]
            else:
                curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
        prev = curr
    return prev[n]

The rolling version uses two arrays of size n+1 instead of a full (m+1) × (n+1) table. For a 1000-char × 1000-char input, the full table is 1 million cells; the rolling version is 2000. Same O(m × n) time, 500× less memory.

Visually, the fill order matters because each cell depends on cells already filled. For LCS / Edit Distance the dependencies are the cell above, to the left, and the diagonal. Iterating row-major fills them in the right order.

10 · Worked example: Coin Change top-down vs bottom-up

LC 322 is the canonical entry point because the same recurrence expresses cleanly both ways. The state is the remaining amount; the transition picks the best coin. The two implementations differ only in control flow.

Top-down (memoised recursion). Read the recurrence as English: "the best way to make amount a is one coin (whichever you pick) plus the best way to make a − c". Translate directly into a recursive function; add a cache keyed by a so each subproblem is solved once.

// Time:  O(amount × len(coins))   — each state computed once
// Space: O(amount)                — cache + recursion stack
// Trace for coins=[1,2,5], amount=11:
//   best(11) calls best(10), best(9), best(6)
//   best(10) calls best(9), best(8), best(5)
//   best(9) ALREADY CACHED on second call — O(1) hit
// Without the cache: 2^11 ≈ 2048 calls. With it: 11 unique subproblems.

Bottom-up (tabulation). Same recurrence, but compute dp[1] first, then dp[2], then dp[3], and so on up to dp[amount]. Each cell reads only cells below it, so by the time you compute dp[a] every dp[a-c] is already final. No recursion stack, easier to space-optimise, slightly faster on most inputs.

// dp[0] = 0
// dp[1] = 1 + dp[0]              = 1  (one 1-coin)
// dp[2] = min(1+dp[1], 1+dp[0])  = 1  (one 2-coin, beating two 1-coins)
// dp[3] = min(1+dp[2], 1+dp[1])  = 2  (1+2)
// dp[4] = min(1+dp[3], 1+dp[2])  = 2  (2+2)
// dp[5] = min(1+dp[4], 1+dp[3], 1+dp[0]) = 1  (one 5-coin wins)
// ...
// dp[11] = 3  (5+5+1)

11 · Worked example: Longest Common Subsequence (LC 1143)

Problem. Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence picks characters in order, not necessarily contiguous.

State. dp[i][j] = LCS length of text1[:i] and text2[:j]. Transition. If the last characters match, extend the LCS by one: dp[i][j] = 1 + dp[i-1][j-1]. Otherwise drop one character from either side: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base case. Empty prefix → LCS is zero.

func longestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                a, b := dp[i-1][j], dp[i][j-1]
                if a > b {
                    dp[i][j] = a
                } else {
                    dp[i][j] = b
                }
            }
        }
    }
    return dp[m][n]
}

Space optimisation. Each dp[i][j] only reads dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. So you only need the previous row plus one cached value: O(min(m, n)) space.

func longestCommonSubsequenceRolling(text1, text2 string) int {
    // Make text2 the shorter one — drives the inner loop and the array size
    if len(text2) > len(text1) {
        text1, text2 = text2, text1
    }
    m, n := len(text1), len(text2)
    prev := make([]int, n+1)
    curr := make([]int, n+1)

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                curr[j] = prev[j-1] + 1
            } else {
                a, b := prev[j], curr[j-1]
                if a > b {
                    curr[j] = a
                } else {
                    curr[j] = b
                }
            }
        }
        prev, curr = curr, prev
        for k := range curr {
            curr[k] = 0
        }
    }
    return prev[n]
}

12 · Hard worked example: Edit Distance (LC 72)

Problem. Given two strings word1 and word2, return the minimum number of single-character insertions, deletions, and substitutions to transform word1 into word2.

State. dp[i][j] = edit distance from word1[:i] to word2[:j]. Transition. If the last characters match, no work is needed: dp[i][j] = dp[i-1][j-1]. Otherwise, the answer is 1 plus the minimum of three options:

• Delete from word1: dp[i-1][j].
• Insert into word1 (matching word2's last char): dp[i][j-1].
• Replace word1's last char with word2's: dp[i-1][j-1].

Base cases. Empty word1 → insert every char of word2 → dp[0][j] = j. Empty word2 → delete every char of word1 → dp[i][0] = i.

func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // Base cases
    for i := 0; i <= m; i++ {
        dp[i][0] = i              // delete i chars
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j              // insert j chars
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]    // match — no edit
            } else {
                del := dp[i-1][j]
                ins := dp[i][j-1]
                rep := dp[i-1][j-1]
                m := del
                if ins < m { m = ins }
                if rep < m { m = rep }
                dp[i][j] = 1 + m
            }
        }
    }
    return dp[m][n]
}

Trace through "horse" → "ros". The optimal edit sequence is delete 'h', replace 'o' with 'r' (no — actually keep 'r', delete 'o', delete 'e', three ops). Let's verify with the table:

        ""  r   o   s
    ""   0  1   2   3
    h    1  1   2   3
    o    2  2   1   2
    r    3  2   2   2
    s    4  3   3   2
    e    5  4   4   3

dp[5][3] = 3. Three operations: delete 'h', delete 'r' (replace was free
once 'r' = 'r'... actually the table shows one way: keep first char as
substitution counter, then proceed). The point isn't the exact ops — it's
that the table gives you the minimum count in O(m × n) time.

13 · How to solve a hard DP problem: step by step

Hard DP problems are won or lost on the modelling, not the code. Seven questions, in order, that turn a confusing prompt into a straightforward implementation.

1. State definition: what does dp[i] (or dp[i][j], or dp[i][j][k]) actually mean? Write it in plain English: "dp[i] = the maximum X considering the first i elements." If you cannot say it cleanly, your state is wrong. Spend two minutes here before writing any code.
2. Recurrence: how does dp[i] relate to smaller indices? What are the choices at position i? Each choice consumes some input and reduces to a smaller subproblem. The recurrence is the function from "best of all choices" to dp[i].
3. Base cases: what are the smallest subproblems you can answer directly? dp[0], dp[empty][empty], dp[i][0] for the row-with-empty-other-string case. Explicit, not implicit; uninitialised cells corrupt everything downstream.
4. Evaluation order: which cells need to be filled before which? For bottom-up, you need every dp[i-1] to be finalised before you compute dp[i]. For 2D DP, decide whether to iterate row-major or column-major; both can be right depending on the recurrence direction.
5. Memoisation or tabulation? Top-down is closer to the recurrence and only computes states you actually need. Bottom-up is faster (no function-call overhead), avoids stack overflow, and gives you room for space optimisation. Pick by interview comfort, not dogma.
6. Space optimisation: can you roll the table? If dp[i] only depends on dp[i-1], two rows are enough. If it only depends on dp[i-1] and dp[i-2], three. Mention it to the interviewer; implement it if asked.
7. Path reconstruction: does the question want the answer or the path? If "the minimum cost", just return dp[final]. If "the sequence that achieves it", walk back from dp[final], tracing which predecessor produced each value. Reconstruction is usually harder than the DP itself.

14 · Five-problem progression

15 · What breaks: the deep list

• Wrong state definition: subtly off-by-one in what "i" means. The single most common DP bug, and the one that wastes most of the interview. "dp[i] = answer for the first i elements" and "dp[i] = answer ending at index i" look identical but have different recurrences. Pick one, write it down, never mix.
• Base cases missing edge values. dp[0], the empty-string case, the zero-amount case: get these explicitly. A wrong base case quietly corrupts every other cell. For 2D, both dp[0][j] and dp[i][0] need attention.
• Evaluation order with the wrong dependency direction. 0/1 knapsack iterates capacity backwards so each item is used at most once; unbounded knapsack iterates forwards so it can be reused. Reversing the inner-loop direction silently turns one problem into the other. Trace through three iterations on paper to confirm.
• Off-by-one in bottom-up loops. Indexing dp[i-1] with i = 0, or forgetting that dp has size n+1 when the problem is 1-indexed. Allocate one extra cell when in doubt.
• Forgetting to initialise the dp array. Especially for min/max problems: uninitialised cells default to whatever your language gives you, which is usually wrong. Initialise to infinity for min, -infinity or 0 for max. In Go, make([]int, n) zero-fills, which is wrong for min problems; initialise explicitly.
• Reconstructing the path is harder than the DP itself. The DP gives you the optimal value; the path requires walking backward from dp[final], comparing each cell against its predecessors to figure out which choice produced it. For LCS, the backtrace is its own O(m + n) walk; for Edit Distance, you need to track which of the four operations applied. Practise this separately; it's a common follow-up.
• Mistaking O(n × W) for O(n) when W is the value, not the input size. Knapsack and coin change are pseudo-polynomial: the runtime is polynomial in the numeric value of W, not in its bit-length. With amount = 10^9, the table doesn't fit in memory.
• Not memoising in top-down. A pure recursion with no cache is just brute force with extra function-call overhead. Map in Go, @lru_cache in Python, an array in Java: make sure it's actually there.
• Recomputing the same subproblem because of unhashable state. If your state involves slices or sets, hashing them as map keys is expensive (Go) or impossible (Python before frozen variants). Convert to tuples / strings / bitmasks before caching.
• Greedy in disguise. Some "DP" problems have a greedy proof that's much faster. House Robber I is DP; Jump Game I is greedy. Always sanity-check whether a local rule works before reaching for the table.

16 · What to say in the interview

1. "Optimal or count → DP." Name the pattern out loud. The interviewer wants to hear you recognise the shape from the prompt.
2. State definition first. The most important step. Say out loud what dp[i] (or dp[i][j]) means in plain English before writing anything. If the state is wrong, nothing downstream will be right.
3. Transition. Write the recurrence. Justify why those are the only choices.
4. Base case. The smallest subproblem you can answer directly. State it explicitly: dp[0] = 0, dp[empty][empty] = 0, etc.
5. Order of computation. For bottom-up, which dimension increases first? Make sure every cell you read has already been written.
6. Complexity. Time is state count × transition cost. For coin change, that's O(amount × len(coins)). Space is the table size, possibly reduced with a rolling window.

17 · Where this gets asked

18 · Complexity, side by side

DP complexity is "state count × cost-per-transition". The table below summarises the dominant archetypes and the time/space wins that come from rolling, memoisation, and special structure.

19 · Memoisation vs tabulation: the dual

Same problem, same recurrence, two implementations. Knowing both and naming the trade-off is a senior signal. Here's the same Coin Change written six ways: recursive (slow), memoised top-down, tabulated bottom-up, rolling bottom-up, and the "what if I optimise one further step" variants, to internalise the duality.

The senior-interview move: write the bottom-up version, then say "the top-down would look like this — let me know if you'd prefer it" (sketch in two lines). This shows you understand the duality without committing to writing both.

20 · The senior modelling trick: when state needs an extra dimension

Mid-interview, the interviewer adds a constraint that breaks your DP. "Cool, that works — now what if you can only do at most 2 transactions?" or "what if there's a cooldown after each operation?". The fix is almost always the same: add a dimension to the state.

21 · Try it yourself

Climbing Stairs · LC 70

The cleanest 1D DP. Hint: dp[i] = dp[i-1] + dp[i-2]. Write it recursive-with-memo first, then convert to bottom-up. Then notice you only need two rolling variables: O(1) space.

House Robber · LC 198

1D DP with a choice at each step. Hint: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). State is "best loot through house i". Roll two variables again. Then try LC 213 (houses in a circle) for the variant.

Coin Change · LC 322

Unbounded knapsack: the canonical "minimum coins to make amount" problem. Hint: dp[a] = min(dp[a - c] + 1) over each coin c. Initialise dp[0] = 0, everything else to amount + 1 (sentinel for unreachable).

Longest Increasing Subsequence · LC 300

The O(n²) DP is the warm-up; the O(n log n) patience-sort version is the follow-up. Hint: dp[i] = 1 + max(dp[j] for j<i if nums[j]<nums[i]). Then for the log-n version, maintain a "tails" array and binary-search each new element's insertion point.

Stretch: Edit Distance · LC 72

Two-string DP. Hint: dp[i][j] = edit_distance(s1[:i], s2[:j]). Three transitions (insert, delete, replace) plus a "match" shortcut when the characters are equal. Draw the table by hand for two short strings to see why the recurrence works.

Further reading

• Kleinberg & Tardos — Algorithm Design, Chapter 6. The best DP introduction in a textbook. The chapter builds from weighted interval scheduling to sequence alignment, deriving each recurrence carefully rather than presenting it.
• CLRS — Chapter 15. The reference treatment. Rod cutting, matrix chain, LCS, optimal BSTs, with the formal proofs of optimal substructure.
• Erickson — Algorithms (free online). Chapter 3 on dynamic programming reads like Kleinberg-Tardos but funnier. The "patterns of DP" framing is the right mental model.
• Adjacent: Recursion. Every DP starts as a recursion. If the recursion isn't clean, the DP won't be either.
• Adjacent: Tree DP. DP where the state is a subtree. Post-order traversal does the work; the recurrence usually fits in one return statement.
• Semicolony: Algorithm visualizer. Step through small DP tables cell by cell. Useful when you can't see why a recurrence isn't filling the way you expect.