Dynamic Programming

Dynamic programming solves problems by breaking them into overlapping subproblems, solving each once, and caching the result.

Elements

A problem suits DP iff:

• Optimal substructure
  An optimal solution to the problem contains optimal solutions to its subproblems.
• Overlapping subproblems
  The same subproblems recur across different recursive branches.

DP vs Divide-and-Conquer

Both decompose a problem recursively.

• Divide-and-conquer
  Subproblems are independent. Results are not reused.
• Dynamic programming
  Subproblems overlap. Results are cached and reused.

Approaches

• Memoization (top-down)
  Solve recursively. Cache each result on first computation and return it directly on repeat calls.
• Tabulation (bottom-up)
  Fill a table from base cases upward in dependency order. No recursion stack.

Requirements

• Problem must be expressible as a recurrence.
• Number of distinct subproblem instances must be polynomially bounded.
• Subproblem dependency graph must be a DAG (no cycles).

Fibonacci Example

Naive recursion recomputes $F(k)$ at every branch: time $O(2^n)$.

Tabulation:

1. Set $dp[0] = 0$, $dp[1] = 1$.
2. For $i = 2$ to $n$: $dp[i] = dp[i-1] + dp[i-2]$.
3. Return $dp[n]$.

Time: $O(n)$. Space: $O(n)$, reducible to $O(1)$ by keeping only the last 2 values.