Dynamic Programming

How to recognize DP, the five-step recipe (state, transition, base, order, answer), memoization vs tabulation, and the classic problem families.

DPmemoizationrecursion

When it's DP

Two signals together: optimal substructure (the answer is built from answers to subproblems) and overlapping subproblems (the same subproblem recurs). If subproblems don't overlap, it's divide-and-conquer, not DP. Phrasings: "number of ways", "min/max cost/length", "can you reach", "longest …".

The five-step recipe

  1. State — what parameters identify a subproblem? (dp[i], dp[i][j]…)
  2. Transition — how does a state combine smaller states?
  3. Base case(s) — the trivial smallest states.
  4. Order — memoized recursion (top-down) or fill a table (bottom-up).
  5. Answer — which state holds it.

Memoization vs tabulation

  • Top-down (memoize): write the recursion, cache results. Easiest to derive — start here in an interview.
  • Bottom-up (tabulate): fill an array in dependency order. No recursion overhead; enables space optimization (keep only the last row/few cells).
Python
# Coin change: fewest coins to make `amount` (unbounded coins).
def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount          # dp[x] = fewest coins to make x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] < INF else -1
# Time O(amount · coins), Space O(amount)

Watch the table fill

This is the part no amount of reading teaches: watch answers to small questions combine into answers to bigger ones. Four problems on one player — start with Fibonacci (the "hello world" of DP), then coin change (where greedy fails and the table doesn't), then the two 2-D classics.

Dynamic programming — Fibonaccitime O(n)space O(n)
0123456789fib

1/19Goal: the 9th Fibonacci number. Naive recursion recomputes the same values millions of times — instead we'll fill a table once, left to right.

problem

Classic families (recognize the skeleton)

FamilyExamplesState shape
1-D sequenceclimbing stairs, house robber, LISdp[i]
Knapsack0/1 knapsack, partition equal subset, coin changedp[i][capacity]
Two stringsedit distance, LCSdp[i][j]
Gridunique paths, min path sumdp[r][c]
Intervalsmatrix-chain, burst balloonsdp[i][j] over ranges
Derive top-down first, then convert

Get the recurrence right with memoization (it mirrors the brute-force you already described), then convert to bottom-up if you need to optimize space. Trying to write the table directly is where people make indexing errors.

Practice — climb the ladder

The DP on-ramp: define the state in ENGLISH first ("dp[i] = best answer using the first i items"), then the recurrence, then the base cases.

Practice ladder: Dynamic Programming — Foundations0/9 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Warm-up

one-dimensional, one decision per step
  1. Climbing StairsEasy

    Fibonacci in costume — your first state definition and recurrence.

  2. Min Cost Climbing StairsEasy

    Same shape plus costs — min() enters the recurrence.

  3. House RobberMedium

    Take-or-skip — THE template for non-adjacent choice problems.

Core

the four state shapes you must recognize
  1. Maximum SubarrayMedium

    Kadane — dp[i] = best ENDING here; extend or restart.

  2. Coin ChangeMedium

    Unbounded choices to reach an amount — min-cost reachability.

  3. Longest Increasing SubsequenceMedium

    dp[i] anchored at index i, scanning back — O(n²) first, patience-sort later.

  4. Unique PathsMedium

    Grid DP — cell = sum of the two cells that can reach it.

Stretch

two sequences = 2D table
  1. Longest Common SubsequenceMedium

    The 2D template — match ⇒ diagonal+1, else max(left, up).

  2. Edit DistanceMedium

    Same table, three operations — the canonical string-transform DP.