Dynamic Programming: Recursion Without Redundancy

The Core Idea

Dynamic programming is not an algorithm. It is a proof technique disguised as a computational method.

The idea: if an optimization problem has optimal substructure (the optimal solution contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur many times), then we can solve it by solving each subproblem once, storing the result, and combining.

This sounds simple. The depth lies in recognizing when a problem has this structure—and in the art of defining the right subproblems.

1. Bellman’s Principle of Optimality

An optimal policy has the property that, whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Formally: if $x_0 \to x_1 \to \cdots \to x_n$ is an optimal trajectory, then $x_k \to x_{k+1} \to \cdots \to x_n$ must be optimal from $x_k$.

Why is this not trivially true? Because it fails for many natural problems:

• Longest simple path: The longest path from $A$ to $C$ through $B$ does not necessarily use the longest path from $A$ to $B$ (it might revisit nodes).
• Any problem with constraints that couple subproblems: If using a resource in the first half limits what’s available in the second half, and the constraint is non-separable, Bellman’s principle breaks.

When it holds, the optimal value function satisfies a recursion (the Bellman equation):

$$V(s) = \min_a \left[c(s, a) + V(f(s, a))\right]$$

Choose the action $a$ that minimizes the immediate cost $c(s, a)$ plus the optimal cost-to-go from the next state $f(s, a)$.

2. The Structure of Recursion: Same as Renewal Theory

The Bellman equation has the same architecture as the Renewal Equation:

$$m(t) = F(t) + \int_0^t m(t - x) \, dF(x)$$

Both decompose a problem into: “handle the first step, then solve the remaining (smaller) instance.”

Concept	Dynamic Programming	Renewal Theory
Decomposition	First action + future cost	First renewal + future count
State	Current position/config	Current time
Recursion	Bellman equation	Renewal equation
Solution	Value function $V(s)$	Renewal function $m(t)$
Limit behavior	Steady-state policy	$N(t)/t \to 1/\mu$

This is not a coincidence. Both are applications of the principle of conditioning on the first step: reduce a complex stochastic or combinatorial problem to “what happens first” + “what’s left.” The mathematical structure is identical; only the domain changes.

3. Memoization vs. Tabulation: Two Philosophies

Top-down (memoization): Write the natural recursion, cache results. Only solve subproblems that are actually reached. Elegant, but carries function call overhead and stack depth limits.

Bottom-up (tabulation): Identify the dependency order, fill the table from smallest subproblems upward. No recursion, no stack, cache-friendly memory access. Requires understanding the full DAG structure.

Both produce the same answers. The choice depends on the subproblem space:

• If the space is sparse (many subproblems never needed), memoization wins.
• If the space is dense (most subproblems needed), tabulation wins.
• If the space is exponential but only polynomially many are reachable, memoization turns exponential brute force into polynomial DP.

4. The Art: Choosing the State

The hardest part of DP is defining the state. The state must capture exactly enough information to make the future independent of the past (the Markov property!). Too little, and the recursion is invalid. Too much, and the state space explodes.

Example: Edit Distance. $\text{dp}[i][j]$ = minimum edits to transform $s_1[1..i]$ into $s_2[1..j]$. The state $(i, j)$ is sufficient because the optimal edit sequence for the first $i$ and $j$ characters doesn’t depend on what comes after. The state space is $O(nm)$—polynomial.

Example: Traveling Salesman. $\text{dp}[S][v]$ = minimum cost path visiting exactly the cities in set $S$, ending at $v$. The state must include the subset $S$ because the future depends on which cities remain. The state space is $O(2^n \cdot n)$—exponential, but better than the naive $O(n!)$.

Example: Knapsack. $\text{dp}[i][w]$ = maximum value using items $1..i$ with capacity $w$. The state captures the remaining capacity, which is all you need to decide about future items. The state space is $O(nW)$—pseudo-polynomial (polynomial in value, exponential in bits).

5. From Optimization to Counting

DP is not only for optimization. Replace $\min$ with $\sum$ and you get counting:

$$C(s) = \sum_a C(f(s, a))$$

• Number of paths in a grid: DP on grid coordinates
• Number of binary trees with $n$ nodes: Catalan number recurrence $C_n = \sum C_k C_{n-1-k}$
• Partition function in statistical physics: sum over configurations weighted by energy

The Bellman equation structure carries over exactly. The change is from $\min/\max$ (optimization) to $\sum$ (counting/expectation). In fact, the renewal function $m(t) = \mathbb{E}[N(t)]$ is exactly this: a counting recurrence averaged over randomness.

6. The Computational Lens: Why DP Matters

DP is the standard proof technique for showing a problem is in P (solvable in polynomial time). The argument is always:

1. Define a polynomial-sized state space.
2. Show the Bellman equation holds (optimal substructure).
3. Show each state depends on already-computed states (no cycles in the dependency DAG).
4. Conclude: polynomial states × polynomial time per state = polynomial total.

Conversely, when no polynomial state space suffices, the problem is likely NP-hard (TSP, graph coloring). DP still helps—it reduces from $O(n!)$ to $O(2^n \text{poly}(n))$—but the exponential barrier remains.

The Takeaway

Dynamic programming is the computational realization of a single principle: decompose, remember, combine. Its power comes not from cleverness in combining, but from the recognition that the same subproblems recur—and that solving them once suffices. The Bellman equation, the renewal equation, and the Markov property are all manifestations of this one idea: the future, given the present, is independent of the past. When this holds, exponential search collapses into polynomial computation.