Skip to content

Dynamic Programming — Introduction#

DP turns exponential recursion into polynomial tabulation by reusing subproblem answers. Full problem catalog: 13. Dynamic Programming (84 problems).

When DP applies#

Both must hold:

  1. Optimal substructure — optimal solution uses optimal subsolutions.
  2. Overlapping subproblems — same subproblem solved many times in naive recursion.

If only (1) holds and choices are locally optimal → try Greedy first. See Greedy vs DP.

Five-step framework#

  1. Define state — what does dp[i] or dp[i][j] mean?
  2. Recurrence — how does dp[i] depend on smaller indices?
  3. Base cases — smallest subproblems with known answers.
  4. Order — fill table so dependencies are ready.
  5. Answer — which cell holds the final result? Reconstruct path if needed.

Top-down vs bottom-up#

Top-down (memo) Bottom-up (tabulation)
Code @cache on recursion Nested loops
Space O(states) + stack O(states) table
Best when Sparse states, quick to write Need full table, space optimize 
from functools import cache

@cache
def dp(i: int) -> int:
    if i == 0:
        return base
    return min(dp(i - 1), dp(i - 2)) + cost[i]

Classic families#

Family State hint Pattern doc
0/1 Knapsack include/exclude item DP § Knapsack
Unbounded knapsack unlimited use Coin Change
LCS / edit distance two string indices DP § LCS
Grid path (row, col) DP § 2D Grid
Linear sequence dp[i] from prior House Robber, LIS
Tree DP return per subtree House Robber III, Cameras
State machine hold/sell/cooldown Stock problems
Bitmask subset as mask TSP, partition

Space optimization#

When dp[i] only needs dp[i-1] and dp[i-2]:

 prev, curr = 0, 1
 for i in range(2, n + 1):
     prev, curr = curr, prev + curr

Knapsack: one row, iterate right-to-left when updating in place.

Common pitfalls#

  • Greedy works — don't over-DP (e.g. activity selection → greedy).
  • State too big — if dimensions exceed ~10⁶, look for structure or math.
  • Wrong order — filling before dependencies are ready gives wrong answers.
  • Forgetting base cases — empty string, zero capacity, leaf nodes.

Starter problems#

Problem LC Why start here
Climbing Stairs 70 1D recurrence
House Robber 198 include/exclude
Coin Change 322 unbounded knapsack
Longest Increasing Subsequence 300 1D + patience sorting
Edit Distance 72 2D classic

All have full solutions in 13. Dynamic Programming.