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.

Core Basics

• Object: overlapping subproblems + optimal substructure; state is the smallest tuple that summarizes the future.
• Implementation: top-down memo vs bottom-up tableau; reconstruct path via parent pointers when needed.
• Staff-level bar: classify linear, interval, knapsack, grid, bitmask families quickly.

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.

Use-case Lens

• Best when: the same subproblems recur and the optimal answer can be built from smaller answers.
• Not for: problems with no overlapping subproblems; divide-and-conquer or greedy may be simpler.
• Main invariant: each DP state has a precise meaning and is computed only from already-known valid states.
• Interview move: define the state in one sentence before writing the recurrence.

Diagram

Step-by-step Visual

Example: Climb 5 stairs when you can take 1 or 2 steps. DP stores answers to smaller versions of the same problem.

Understanding

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})).

Memory Hooks

• Operational mantra: define state, choose transition, set base cases, then fill in dependency order.
• Anti-panic: define the state sentence before recurrence: "dp[...] means the best/count/possible answer for ..."

Study Pattern (SDE3+)

• Recognition drill (10 min): identify state dimensions and dependency direction from constraints only.
• Implementation sprint (25 min): code one 1D recurrence and one 2D string/grid table; fill base cases out loud.
• Staff follow-up (10 min): discuss space compression, memo vs tabulation, reconstruction, and greedy counterexamples.

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.