Dynamic Programming, from first principles

01 · Foundation

Why does DP exist at all?

Take the classic recursive Fibonacci function: fib(n) = fib(n-1) + fib(n-2). It's correct, but if you actually draw out every call it makes, something wasteful shows up immediately — the same smaller subproblem gets solved again and again from scratch.

Below is the full call tree for fib(4). Notice fib(2) appears twice, as two completely separate branches that each redo the same work:

02 · Recognizing DP

The two properties every DP problem has

A problem is worth solving with DP only when it has both of these. Miss one and DP either won't help or won't even be correct.

• Overlapping subproblems — breaking the problem down produces the same smaller subproblem more than once (just like fib(2) above). If every subproblem is unique, memoizing buys you nothing.
• Optimal substructure — the optimal answer to the big problem can be built directly from optimal answers to its smaller subproblems. For Coin Change: the fewest coins to make amount n is 1 + (fewest coins to make n − coin) for whichever coin gives the smallest result. If the best answer to the whole problem didn't depend on the best answers to its pieces, reusing subproblem answers wouldn't guarantee a correct final answer.

03 · Implementation

Two ways to apply it: Top-Down vs Bottom-Up

Same idea, opposite direction. Top-down starts from the big question and recurses downward, caching as it goes. Bottom-up starts from the smallest subproblems and builds upward until it reaches the answer you actually wanted.

memo = {}
def solve(state):
    if state in base_cases:
        return base_case_value
    if state in memo:
        return memo[state]
    memo[state] = combine(
        solve(smaller_state_1),
        solve(smaller_state_2)
    )
    return memo[state]

dp = [base_case] * (n + 1)
for i in range(1, n + 1):
    dp[i] = combine(
        dp[i - 1],
        dp[i - 2]
    )
return dp[n]

Neither is "more correct" — bottom-up is usually a little faster (no call-stack overhead) and easier to space-optimize; top-down is usually faster to write because it mirrors how you'd explain the recurrence out loud. Every visualizer on this site lets you toggle between both so you can watch the same problem solved both ways.

04 · Method

A repeatable framework for any DP problem

This is the actual sequence to work through, in order, whether the problem is Fibonacci or something you've never seen before.

1. 1 Define the stateWhat minimal set of variables uniquely describes a subproblem? For Coin Change it's just "remaining amount." For LCS it's "how far along string A and string B."
2. 2 Write the recurrenceHow does the answer for a state relate to answers for smaller states? This is the "optimal substructure" step made concrete — usually a min/max/sum over a couple of choices.
3. 3 Identify the base casesThe smallest states you can answer directly, with no recursion — amount 0 needs 0 coins, an empty string has 0 common subsequence, etc.
4. 4 Decide computation orderIf going bottom-up: make sure every dp[i] you fill only depends on dp[j] values that are already filled by the time you get there.
5. 5 Optimize space (optional)If dp[i] only ever depends on the last one or two rows/values, you often don't need the full table — a couple of rolling variables is enough.

05 · Patterns

Common DP patterns you'll keep seeing

Most interview DP problems are a variation on a small number of underlying shapes. Recognize the shape, and half the problem is already solved. Each card links to the matching interactive visualizer.

06 · Worked example

Coin Change, one array cell at a time

Coins [1, 2, 5], target amount 6. State: dp[a] = fewest coins needed to make amount a. Recurrence: dp[a] = min(dp[a-c] + 1) over every coin c ≤ a. Base case: dp[0] = 0 (zero coins needed to make zero).

dp[6] (outlined) checks all three coins: dp[5]+1 = 2, dp[4]+1 = 3, dp[1]+1 = 2 — the smallest is 2, meaning amount 6 is reachable in 2 coins (a 5 and a 1). Every earlier cell was filled the exact same way, only reaching back to cells that were already solved — which is only safe because we filled left-to-right, so dp[a-c] is always already computed by the time we need it.

Open the Coin Change visualizer to watch this table fill animate step by step, in both Bottom-Up and Top-Down mode.

07 · Complexity

How to reason about time & space

The fast way to estimate a DP solution's time complexity, without tracing every call: (number of distinct states) × (work done per state).

• Coin Change — states: one per amount (O(amount)). Work per state: try each coin (O(coins)). Total: O(amount × coins).
• LCS / Edit Distance — states: one per (i, j) pair (O(n × m)). Work per state: constant-time comparison. Total: O(n × m).
• 0/1 Knapsack — states: one per (item, remaining capacity) pair (O(items × capacity)). Work per state: constant (take it or don't). Total: O(items × capacity).

Space follows the same logic — one memo/table slot per state, unless you notice each state only ever needs the last row (or last couple of values), in which case you can drop a 2D table down to one rolling row, or a 1D array down to a couple of variables.

08 · Before you start coding

Common mistakes & how to spot a DP problem

• Defining the state with more variables than necessary — extra dimensions you don't actually need make the table (and the bugs) bigger than they should be.
• Getting the iteration order wrong in bottom-up, so a cell tries to read a value that hasn't been filled yet.
• Forgetting a base case — the recurrence alone is meaningless without a place for it to stop.
• Reaching for DP when there's no overlapping subproblem — if nothing repeats, you're just adding a cache for no benefit.
• Words like "minimum/maximum number of ways," "longest/shortest," or "is it possible to reach exactly N" in a problem statement are strong hints it's DP.
• If the problem naturally breaks into choices at each step ("take it or skip it," "use this coin or don't") and asks for an optimal outcome, that's the include/exclude shape from the patterns above.