Dynamic Programming: A Mental Model That Sticks

Dynamic programming is often taught as a catalog: Fibonacci, knapsack, longest common subsequence, coin change. That approach makes every new problem feel like a memory test. If the input does not resemble a familiar example, the technique seems to disappear.

A better mental model is simpler: dynamic programming evaluates a directed acyclic graph of reusable subproblems. A state names one node. A transition names its outgoing dependencies. Base cases are nodes whose answers are already known. Memoization and tabulation are merely two schedules for evaluating the same graph.

This view turns DP from a bag of tricks into a design process. It also explains details that templates hide: why a state needs certain variables, why loop direction matters, when a greedy choice is unsafe, how to recover the actual solution, and where time and memory complexity come from.

See the Hidden DAG #

Suppose we want the cheapest path from the top-left to the bottom-right of a rectangular cost grid. From each cell we may move only right or down. A naive recursive search branches at every cell and repeatedly solves the same suffix paths.

Let $F(r,c)$ mean the minimum cost of a path that starts at cell $(r,c)$ and ends at the destination, including both endpoints. Then the recurrence is

The destination is a base case:

Positions outside the grid have cost $\infty$, so they can never win the minimum. The important insight is not the formula itself. It is that calls such as $F(1,1)$ can be reached through several paths, yet their answers depend only on their coordinates. Those repeated calls are shared nodes in a DAG.

The graph is acyclic because every move increases either the row or the column. A valid evaluation order must compute every dependency before the state that uses it. Top-down recursion discovers that order on demand. Bottom-up loops state it explicitly.

This model also clarifies the difference between DP and divide-and-conquer. Merge sort creates mostly disjoint subproblems, so caching would add little. DP becomes valuable when branches converge on the same states. If there are $S$ reachable states and at most $T$ transition work per state, the usual bound is

That equation is more reliable than counting recursive calls in an uncached tree.

Design the State Before the Code #

The hardest part of DP is usually deciding what a state means. A useful state is a complete, minimal summary of the past: complete enough that the future answer depends only on the state, but minimal enough that equivalent histories merge.

Use this sentence as a design tool: dp(state) returns …. If the sentence is ambiguous, the implementation will be ambiguous too. For the grid problem, solve(row, col) returns the minimum remaining cost from (row, col), including the current cell. That wording determines the transition and prevents accidentally counting the current cell twice.

Consider what would happen if movement also depended on how many obstacle removals remained. Coordinates alone would no longer be complete. Two visits to (r, c) with different remaining budgets have different possible futures, so the state must become (r, c, removalsLeft). Conversely, storing the entire path prefix would be complete but not minimal: many prefixes with the same position and budget would fail to merge.

A practical state-design sequence is:

1. Identify the decision boundary: what choice is made next?
2. List facts from the past that can change valid future choices or their cost.
3. Remove facts that can be derived from other state variables.
4. Write the return-value sentence, including whether endpoints are counted.
5. Try to produce two histories with the same proposed state but different futures. If you can, the state is incomplete.

State choice controls complexity. A state (index, remainingCapacity) for 0/1 knapsack yields roughly $nW$ nodes, where $W$ is capacity. Adding an unnecessary accumulated value can multiply the graph without changing decisions. Omitting remainingCapacity merges incompatible histories and produces wrong answers.

It helps to specify the recurrence before choosing top-down or bottom-up code. For each state, write four items: meaning, transitions, base cases, and invalid cases. Only then choose storage and evaluation order. This separates the mathematical model from implementation mechanics.

Evaluate Top Down with Memoization #

Memoization preserves the recursive definition. It is often the best first implementation because the control flow resembles the recurrence, unreachable states are never computed, and correctness is easier to reason about locally.

type Position = Readonly<{ row: number; col: number }>;

type PathResult = Readonly<{
  cost: number;
  path: ReadonlyArray<Position>;
}>;

export function minPathMemo(grid: ReadonlyArray<ReadonlyArray<number>>): PathResult | null {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  if (rows === 0 || cols === 0 || grid.some((row) => row.length !== cols)) {
    return null;
  }

  const memo: Array<Array<number | undefined>> = Array.from(
    { length: rows },
    () => Array<number | undefined>(cols),
  );

  function solve(row: number, col: number): number {
    if (row >= rows || col >= cols) return Number.POSITIVE_INFINITY;
    if (row === rows - 1 && col === cols - 1) return grid[row]![col]!;

    const cached = memo[row]![col];
    if (cached !== undefined) return cached;

    const bestSuffix = Math.min(solve(row + 1, col), solve(row, col + 1));
    const result = grid[row]![col]! + bestSuffix;
    memo[row]![col] = result;
    return result;
  }

  const cost = solve(0, 0);
  const path: Position[] = [];
  let row = 0;
  let col = 0;

  while (true) {
    path.push({ row, col });
    if (row === rows - 1 && col === cols - 1) break;

    const down = solve(row + 1, col);
    const right = solve(row, col + 1);
    if (right <= down) col += 1;
    else row += 1;
  }

  return { cost, path };
}

The cache check must distinguish “not computed” from a legitimate answer. Testing if (memo[row][col]) would fail for zero-cost states. undefined is an explicit sentinel, while Infinity represents an invalid transition. Those meanings should not be mixed.

Reconstruction reuses the value function. At each cell, it follows a successor whose optimal suffix produced the current answer. The tie rule right <= down makes output deterministic; choosing down on ties would still be optimal. An alternative is to store a parent or next-move pointer while computing each state. Recomputing the two cached child values saves a second matrix without changing the asymptotic cost.

There are at most $RC$ reachable states, each doing constant work, so time is $O(RC)$ and memo storage is $O(RC)$. The recursion stack can reach $O(R+C)$. That stack is a practical reason to prefer tabulation for very deep state graphs, even when both forms have the same big-O bound.

Evaluate Bottom Up with Tabulation #

Tabulation chooses a topological order explicitly. Because dp[row][col] depends on the cell below and the cell to the right, rows and columns must be visited in reverse. Changing loop direction without changing the state meaning reads values before they exist.

type Move = 'right' | 'down' | 'done';

export function minPathTable(grid: ReadonlyArray<ReadonlyArray<number>>): PathResult | null {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  if (rows === 0 || cols === 0 || grid.some((row) => row.length !== cols)) {
    return null;
  }

  const dp = Array.from({ length: rows }, () => Array<number>(cols).fill(0));
  const next = Array.from({ length: rows }, () => Array<Move>(cols).fill('done'));

  for (let row = rows - 1; row >= 0; row -= 1) {
    for (let col = cols - 1; col >= 0; col -= 1) {
      if (row === rows - 1 && col === cols - 1) {
        dp[row]![col] = grid[row]![col]!;
        continue;
      }

      const down = row + 1 < rows ? dp[row + 1]![col]! : Number.POSITIVE_INFINITY;
      const right = col + 1 < cols ? dp[row]![col + 1]! : Number.POSITIVE_INFINITY;

      if (right <= down) {
        dp[row]![col] = grid[row]![col]! + right;
        next[row]![col] = 'right';
      } else {
        dp[row]![col] = grid[row]![col]! + down;
        next[row]![col] = 'down';
      }
    }
  }

  const path: Position[] = [];
  let row = 0;
  let col = 0;
  while (true) {
    path.push({ row, col });
    const move = next[row]![col]!;
    if (move === 'done') break;
    if (move === 'right') col += 1;
    else row += 1;
  }

  return { cost: dp[0]![0]!, path };
}

The value table and memoized function represent the same nodes and edges. Their differences are operational:

If only the minimum cost were required, the table could be compressed to one row because each iteration needs only the current row to the right and the next row below. Space would fall to $O(C)$. But the next matrix is still $O(RC)$ if the complete path must be reconstructed. Space optimization is therefore an interface decision, not a reflex: returning a witness may require retaining information that a scalar optimum does not.

Diagnose Mistakes from the Model #

Most DP bugs are specification bugs wearing an indexing costume. The model provides a systematic way to find them.

An incomplete state merges situations with different futures. If a stock-trading recurrence limits transactions but the state stores only the day, it cannot distinguish how many transactions remain. Add exactly the information that changes future options.

A bloated state preserves irrelevant history. Carrying the complete chosen item list inside a knapsack cache prevents equivalent subproblems from merging and makes keys expensive. Cache the optimal value by minimal state; store compact choices separately for reconstruction.

Inconsistent meanings cause off-by-one errors. “Best answer through index i” and “best answer starting at index i” need opposite transitions and evaluation orders. Write the return-value sentence beside the recurrence before touching loops.

Missing or overlapping base cases often hide at empty inputs and boundaries. Test the smallest legal instance, an instance with one available move, and an instance where every normal transition is invalid. A base case should return a mathematically complete answer, not merely stop recursion.

Wrong iteration order violates dependencies. Draw one edge from a state to a child. In tabulation, the child must be evaluated first. This also explains the famous 0/1 knapsack rule: updating capacity from high to low prevents the current item from being reused; iterating low to high changes the graph into unbounded knapsack.

Using greedy reasoning without proof discards branches before knowing their future cost. DP compares complete subproblem values. Greedy is safe only when an exchange argument or another proof shows that a locally preferred choice can belong to an optimum.

For debugging, compare memoization and tabulation on tiny random inputs, then check both against brute force. A brute-force solver is too slow for production but excellent as an oracle for grids of three or four cells per side. When results disagree, print state meanings and dependencies, not just the final arrays.

Practice the Design Loop #

DP skill grows faster through controlled variation than through collecting solutions. For each practice problem, spend most of the time on a one-page specification before coding:

1. Write the brute-force choices. This reveals the recurrence tree.
2. Name the state and complete the sentence “this function returns …”.
3. Mark repeated states and estimate their count.
4. Define transitions, valid ranges, base cases, and impossible-state sentinels.
5. Implement memoization first and test against tiny exhaustive cases.
6. Derive a tabulation order by reversing every dependency edge.
7. Add reconstruction, then consider space compression only if the required output permits it.

After solving, change one constraint. Allow diagonal grid moves. Add blocked cells. Ask for the number of optimal paths as well as their cost. Limit obstacle removals. Each change forces you to decide whether the state is still complete and whether the old evaluation order remains valid. That decision-making is the transferable skill.

A useful review ritual is to explain complexity by counting the graph: number of reachable states, transitions examined per state, retained values, and maximum recursion depth. Avoid saying “there are two loops, so it is quadratic.” A three-dimensional state can be cubic with one visible loop, while a two-dimensional table may process only a sparse reachable subset.

The durable takeaway is compact:

• A state is the smallest complete summary needed to determine the future.
• A transition lists the smaller states available after one decision.
• Base cases are already-solved nodes, and invalid cases encode impossible edges.
• Memoization discovers the dependency DAG top down; tabulation evaluates it in an explicit topological order.
• Reconstruction records or replays which transition achieved the optimum.
• Complexity comes from counting states and work per state, not from the surface shape of the code.

Once those pieces are explicit, dynamic programming stops being a pattern to recognize. It becomes a graph you can design, evaluate, test, and explain.