Dynamic Programming

Why This Matters

Dynamic programming turns repeated recursive work into stored subproblem answers. It appears in edit distance, knapsack, sequence alignment, parsing, shortest paths, planning, and value iteration.

The skill is not memorizing a list of famous problems. The skill is designing the state and recurrence.

Learning Objectives

By the end, you should be able to:

Identify overlapping subproblems and optimal substructure.
Define a DP state, base cases, recurrence, and fill order.
Compare memoization, tabulation, and space-optimized DP.
Explain why memoization changes repeated recursion into a bounded set of stored states.
Recognize when greedy, divide-and-conquer, or plain search is a better fit than DP.

Core Idea

Use DP when a problem has overlapping subproblems and a recurrence that combines smaller answers into larger answers.

Style	Direction	Strength	Risk
Memoization	top-down recursion	close to natural recurrence	recursion overhead, cache keys
Tabulation	bottom-up iteration	explicit order, often faster	table design can be awkward
Space-optimized DP	keep only needed rows/states	lower memory	easier to corrupt dependencies
Greedy	choose local best once	simpler when valid	fails without exchange property

Non-Example or Failure Mode

Binary search is not dynamic programming. It has a shrinking search interval, but it does not solve overlapping subproblems whose answers should be stored and reused.

The common failure mode is using DP as a label for any recursive solution. If subproblems do not repeat, memoization adds memory and complexity without reducing the asymptotic work.

Worked Example

Fibonacci is the smallest DP example because naive recursion recomputes the same states.

function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

The state is n. The recurrence is fib(n) = fib(n - 1) + fib(n - 2). Memoization changes exponential repeated recursion into O(n) stored states.

For edit distance, the state becomes (i, j): the answer for prefixes a[0..i) and b[0..j).

Builder Connections

Text systems use edit distance and sequence alignment ideas.
Reinforcement learning uses dynamic programming in value iteration.
Parsers use DP for chart parsing.
Route planning uses shortest-path recurrences.
Systems code uses DP-like caching whenever repeated subproblems are expensive and inputs are stable.

Common Mistakes

Mistake	Correction
Starting with code before defining the state.	Name the state, base cases, recurrence, and fill order before implementation.
Using DP without overlapping subproblems.	Memoization only helps when the same subproblem can occur multiple times.
Forgetting base cases.	Base cases anchor the recurrence and prevent undefined table reads.
Storing too much state.	Keep only variables needed to determine future transitions.
Updating in the wrong order.	Space optimization must preserve dependencies that later states still need.

Diagnostic Questions

Question type	Question	Answer signal
Definition	What is the state?	The minimal information that identifies a subproblem, such as `n` or `(i, j)`.
Example / non-example	Does binary search need DP?	No. Its subproblems do not overlap; it discards half the search space.
Computation	How many states are in an edit-distance table for lengths `m` and `n`?	`(m + 1)(n + 1)` states including empty-prefix base cases.
Proof	Why does memoized Fibonacci compute each state once?	After `fib(k)` is stored, future calls return from the memo table instead of recursing.
Transfer	How is value iteration a DP idea?	It repeatedly updates value estimates from successor states using a Bellman recurrence.

Exercises

Beginner:

Identify the DP state for Fibonacci.
Fill a 3 by 3 edit-distance table.
Write base cases for climbing stairs with one-step or two-step moves.

Intermediate:

Derive the recurrence for 0/1 knapsack.
Convert memoized Fibonacci into tabulation.

Challenge:

Implement value iteration on a tiny gridworld and explain the state transition.

Diagram Recommendation

Type: subproblem grid.

Caption: "Edit distance table filled from base cases toward the final answer."

Purpose: Show that DP is dependency order over states, not a magic code pattern.

Implementation Task

Implement edit distance with a two-dimensional table.

function editDistance(a: string, b: string) {
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0),
  );
  for (let i = 0; i <= a.length; i += 1) dp[i]![0] = i;
  for (let j = 0; j <= b.length; j += 1) dp[0]![j] = j;
  for (let i = 1; i <= a.length; i += 1) {
    for (let j = 1; j <= b.length; j += 1) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      dp[i]![j] = Math.min(
        dp[i - 1]![j]! + 1,
        dp[i]![j - 1]! + 1,
        dp[i - 1]![j - 1]! + cost,
      );
    }
  }
  return dp[a.length]![b.length]!;
}

Then reduce memory to two rows and explain which dependencies survive.

Next Topics

References

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 14.
MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.
MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015.
Kleinberg and Tardos. Algorithm Design (2005). Ch. 6.