18. Dynamic Programming

TL;DR

When optimal solutions reuse overlapping subproblems and optimal substructure, memoize or fill a table in a safe order instead of recomputing exponential recursion. The meta-pipeline: pick state (what you must remember), write recurrence, set base cases, choose iteration order (so dependencies are ready), then read the answer from the right cell(s). Large families—linear 1D, grids, knapsacks, LIS, LCS, edit distance, intervals on segments, small-(n) bitmask subsets, digit DP—are the same recipe with different state dimensions.

Recognition Cues

• Phrases: "minimum/maximum ways", "count ways", "optimal", "can you reuse", "overlapping subproblems", "string alignment", "longest increasing", "fill a matrix", "choose items with weight", "burst balloons", "numbers in range with digit constraint".
• Shapes: decision at each index depends on earlier decisions; two strings; interval [left, right] on an array; set of small items with bitmask; numeric bounds for digit-by-digit construction.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

State is a sufficient statistic of the past for future optimality. Recurrence links a cell to a bounded neighborhood (previous index, left neighbor, knapsack capacity knelt from above, etc.). Topological order for dependency DAG: in 1D forward DP, earlier indices first; in 2D, row-major or problem-specific; interval DP increases length; digit DP goes from most significant to least with tight flags.

Generic Recipe

1. Define state — arguments that fully describe a subproblem (e.g. index, sumSoFar, mask, tight).
2. Recurrence — express answer in terms of strictly smaller / previously solved substates.
3. Base cases — smallest subproblems with concrete values.
4. Iteration order — top-down with memo map keyed by state tuple, or bottom-up loops that respect dependencies.
5. Answer — memo[n] or table[n][m] or best over terminal states; sometimes min/max over last layer.

Complexity

• Time/space: states × work per state. Linear DP often (O(n)) or (O(n \cdot W)) for knapsack capacity W. Grid (O(n \cdot m)). Interval (O(n^3)) naive. Bitmask (O(2^n \cdot n)). Digit DP (O(\text{digits} \cdot 10 \cdot \text{flags})).

Generic Code Template

Go

package main

// Top-down with memo: climb stairs (1 or 2 steps) — state = current step.
func climbWaysTopDown(topStep int, memo map[int]int) int {
	var dfs func(step int) int
	dfs = func(step int) int {
		if step == topStep {
			return 1
		}
		if step > topStep {
			return 0
		}
		if stored, ok := memo[step]; ok {
			return stored
		}
		memo[step] = dfs(step+1) + dfs(step+2)
		return memo[step]
	}
	return dfs(0)
}

// Bottom-up: knapsack unbounded one dimension (coin change style).
func minCoinsBottomUp(target int, coins []int) int {
	table := make([]int, target+1)
	for amount := 1; amount <= target; amount++ {
		table[amount] = target + 1
		for _, coin := range coins {
			if coin <= amount {
				candidate := table[amount-coin] + 1
				if candidate < table[amount] {
					table[amount] = candidate
				}
			}
		}
	}
	if table[target] > target {
		return -1
	}
	return table[target]
}

func main() {}

JavaScript

function climbWaysTopDown(topStep, memo = new Map()) {
  function dfs(step) {
    if (step === topStep) {
      return 1;
    }
    if (step > topStep) {
      return 0;
    }
    if (memo.has(step)) {
      return memo.get(step);
    }
    const total = dfs(step + 1) + dfs(step + 2);
    memo.set(step, total);
    return total;
  }
  return dfs(0);
}

function minCoinsBottomUp(target, coins) {
  const table = new Array(target + 1).fill(target + 1);
  table[0] = 0;
  for (let amount = 1; amount <= target; amount += 1) {
    for (const coin of coins) {
      if (coin <= amount) {
        table[amount] = Math.min(table[amount], table[amount - coin] + 1);
      }
    }
  }
  return table[target] > target ? -1 : table[target];
}

Variants

Representative Problems

• 070. Climbing Stairs — linear recurrence baseline
• 322. Coin Change — unbounded knapsack
• 1143. Longest Common Subsequence — 2D string DP

Anti-patterns

• Recursing without memo on overlapping subproblems (pure exponential).
• Wrong order (using uninitialized cells in bottom-up).
• Off-by-one in knapsack inner loop (0/1 goes backward on capacity, unbounded forward).
• Bitmask DP when n is large enough to break (2^n) time—need different model (greedy, meet-in-the-middle with care).
• Confusing greedy with DP—prove optimality or use DP when counterexamples exist.