Dynamic Programming

How dynamic programming works

DP applies when a problem has two properties:

1. Optimal substructure. The optimal solution can be built from optimal solutions to smaller versions of the same problem.
2. Overlapping subproblems. The same smaller problem appears many times across the recursion.

The technique: define a recurrence in terms of smaller subproblems, then either memoize the recursive function (top-down) or fill a table iteratively from base cases up (bottom-up). Both turn exponential recursion into polynomial work because each subproblem is solved exactly once.

Top-down vs bottom-up

The two flavors give the same time complexity but differ in style and constants:

	Top-down (memoization)	Bottom-up (tabulation)
Direction	Original → subproblems	Base cases → original
Drives which subproblems get computed	Recursion does it for you	You decide the iteration order
Code style	Recursive function + cache	Loop + array
Stack usage	O(depth) recursion stack	O(1) extra (no recursion)
Natural for	Tree-shaped problems	Linear / grid problems
Speedup over naive	Same Big-O, ~2× constant	Same Big-O, faster in practice
Easier to write when	Recurrence is natural	State transitions are simple

Use top-down when you want the code to read like the recurrence; use bottom-up when you want the lowest constant factors and don't mind thinking about iteration order. Many production solutions are bottom-up because the savings on overhead matter at scale.

Canonical example: climbing stairs

You're at the bottom of a staircase with n steps. Each move you can take 1 or 2 steps. How many distinct ways are there to reach the top?

Recurrence: ways(n) = ways(n-1) + ways(n-2) (last step was 1 or 2). Base cases: ways(0) = 1, ways(1) = 1. Notice this is just Fibonacci.

// Naive recursive — O(2^n)
function climbNaive(n) {
  if (n < 2) return 1;
  return climbNaive(n - 1) + climbNaive(n - 2);
}

// Top-down (memoized) — O(n)
function climbMemo(n, memo = {}) {
  if (n < 2) return 1;
  if (memo[n]) return memo[n];
  return memo[n] = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
}

// Bottom-up (tabulated) — O(n) time, O(1) space
function climbDP(n) {
  let prev = 1, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

For n = 50, the naive version takes ~2^50 ≈ 10^15 calls (years to run). The memoized version takes 50 calls. The bottom-up version uses 2 variables. Same problem, three orders of magnitude in performance.

When to use DP

Look for these patterns in the problem statement:

• "Optimal" something. Maximum, minimum, longest, shortest. The problem is asking for the best among many possible solutions.
• Counting paths or arrangements. "How many ways to..." problems.
• Recursive structure with repeated subproblems. If your recursion tree is doing the same work multiple times, that's the sign.
• Sequence problems. Longest increasing subsequence, edit distance, longest common subsequence — anything operating on prefixes or suffixes of strings/arrays.
• Choice with constraints. Knapsack, coin change, partition problems — choose items subject to a budget or constraint.

If the problem doesn't have overlapping subproblems, DP gives no speedup. Try greedy or divide-and-conquer first.

Famous DP problems

0/1 Knapsack

Items with weights w[i] and values v[i], capacity W. Maximize value without exceeding capacity. Each item can be taken or skipped.

function knapsack(weights, values, W) {
  const n = weights.length;
  // dp[i][w] = max value using first i items with capacity w
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i-1][w]; // skip item i
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
      }
    }
  }
  return dp[n][W];
}

O(n × W) time, O(n × W) space. The space can be reduced to O(W) by noting that row i only depends on row i-1.

Longest Common Subsequence

function lcs(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i-1] === b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}

Runs in O(m × n). Used for diff tools, version control merges, DNA sequence alignment.

Python DP idioms

from functools import lru_cache

# Top-down with @lru_cache — Python's built-in memoization
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

# Bottom-up — typically more idiomatic in Python
def coin_change(coins, amount):
    """Min coins to make amount; -1 if impossible."""
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Space optimization tricks

• Roll the table. If dp[i] only depends on dp[i-1] (or some bounded number of previous rows), keep only those rows. The fib bottom-up keeps 2 variables instead of an n-element array.
• In-place updates. For 1D problems where dp[i] depends on dp[i - delta], you can sometimes update the array in place in the right iteration order.
• Bitmask DP for small subsets. If the state is "which subset of n elements is included," for n ≤ 20 you can encode the subset as a 32-bit integer. dp[mask] is then a 1D array of size 2^n.

Common bugs and edge cases

• Wrong base cases. The most common DP bug — getting the iteration started incorrectly. Always test with the smallest input where the answer is known by inspection.
• Wrong iteration order. If dp[i] depends on dp[i-1] and dp[i-2], you must compute lower indices before higher ones. Reversing the order silently gives wrong answers.
• Off-by-one in the table dimensions. Knapsack's table has dimensions (n + 1) × (W + 1) — extra row and column for the empty / zero-capacity cases. Forgetting either causes index-out-of-bounds at the boundaries.
• Trying DP when greedy works. If the problem has the greedy choice property, DP is correct but unnecessarily complex. Try greedy first; if it fails on a small adversarial example, fall back to DP.
• Trying DP when there are no overlapping subproblems. Adding memoization to a function that's already only called once with each input does nothing. Profile first; verify the same subproblem is hit many times before optimizing.