Dynamic Programming Visualized

Dynamic programming is not “store old answers.” It is a way to solve a problem when subproblem results can be reused and a state captures everything future choices need to know. The difficult part is usually defining that state correctly.

Start with repeated work

The naive Fibonacci recurrence exposes the pattern:

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  └─ fib(2)
└─ fib(3)
   ├─ fib(2)
   └─ fib(1)

fib(3) and fib(2) are computed more than once. These are overlapping subproblems. A recursion tree with enough repetition may be a candidate for dynamic programming, but repetition alone is not enough: the solution must also have a useful state and a recurrence that combines correct smaller answers.

Three versions of the same recurrence

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  const known = memo.get(n);
  if (known !== undefined) return known;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

function fibTable(n: number): number {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

Naive recursion recomputes states and takes exponential time. Memoization is top-down: retain a result when a recursive call first computes it, then return the cached value on later visits. Tabulation is bottom-up: choose an order where every dependency exists before a state is filled.

State design is the real work

For Fibonacci, dp[i] means “the ith Fibonacci number.” It is sufficient because future values need only the two prior values. A richer problem needs a richer state.

Consider 0/1 knapsack: each item can be used at most once, each has a weight and value, and the bag has capacity c. A useful definition is:

For item i, either skip it or take it when it fits:

The prior item count is essential. A state such as dp[c] can still work after careful optimization, but then capacity must iterate backward; moving forward would let the same item be used multiple times. That is a state/lifecycle bug, not a syntax issue.

Optimal substructure and order

Optimal substructure means an optimal whole solution can be assembled from optimal subproblem choices under the selected state. It does not mean every recursive problem wants DP. First identify the decision, identify what affects future legal choices, and prove that the recurrence preserves the problem's constraints.

Memoization is useful when only a small portion of a large state space is visited or recursion maps directly to the definition. Tabulation is useful when an iterative dependency order is clear and avoiding recursion depth matters. Either can be wrong when it caches too little information, uses an incorrect base case, or iterates in an order that sees values from the wrong stage.

When not to use it

Do not add DP to a simple linear scan, a problem with no repeated states, or a case where a greedy proof is available. Be cautious when the state space itself is enormous—subsets, dimensions, capacities, and coordinates multiply quickly. Memory can become the limiting cost before time does.

Connections

Recursion gives the first recurrence and exposes repeated calls. Big O measures the transformation from exponential repeated work to a bounded number of states. Graph algorithms sometimes use DP on a DAG, but only when the dependency direction and state match the task.

Summary

Dynamic programming is a disciplined state model plus reuse. Choose what dp[...] means, prove the recurrence, establish base cases, and select a legal dependency order. The visualizer runs one Fibonacci input through all three strategies so repeated work and cache reuse are visible rather than implied.