Dynamic Programming (DP)

Dynamic Programming (DP) resolves combinatorial explosions by decomposing complex optimization problems into a directed acyclic graph of overlapping subproblems, computing each state exactly once and reusing tabular results. From compiler instruction scheduling and relational query planners to sequence alignment in computational genomics, DP bridges mathematical induction and cached tabular execution.

Dynamic Programming is an algorithmic paradigm designed to optimize recursive search spaces by identifying shared subproblems, imposing a topological evaluation order, and caching intermediate states in memory.

By the end of this chapter, you will be able to:

1. Formulate Formal State Definitions: Isolate the minimal tuple $(i,w)$ capturing sufficient history and derive recurrences conforming to Bellman's Principle of Optimality.
2. Evaluate Architecture Trade-Offs: Contrast Top-Down Memoization (lazy recursion) with Bottom-Up Tabulation (eager iteration) across memory overhead, recursion limits, and cache locality.
3. Trace Multi-Dimensional State Matrices: Manually construct tabular matrices for 0/1 Knapsack and Longest Common Subsequence (LCS) and reconstruct optimal solution subsets via backwards pointer tracking.
4. Prove Space-Optimization Invariants: Mathematically prove why compressing a 2D state matrix to a 1D buffer requires strictly descending capacity iteration to enforce 0/1 single-use constraints.
5. Analyze Pseudo-Polynomial Complexity: Differentiate between polynomial and pseudo-polynomial time complexities, analyzing the impact of numeric input magnitudes on bit-length complexity.

Formulated by Richard Bellman in 1957, dynamic programming applies strictly to problems exhibiting two core structural properties:

• Divide and Conquer (e.g., Merge Sort, Strassen Matrix Multiplication): Partitions problems into independent, non-overlapping subproblems, solves each independently, and combines their solutions.
• Greedy Algorithms (e.g., Dijkstra, Kruskal, Huffman Coding): Commits irrevocably to a locally optimal choice at each step without exploring alternative branches, requiring the greedy-choice property and optimal substructure. When greedy decisions can lead to suboptimal dead ends, dynamic programming explores all candidate state transitions.

Every dynamic programming problem can be operationalized through two complementary execution strategies:

Every dynamic programming algorithm is engineered through a disciplined four-step protocol:

1. State Characterization: Define the state tuple $dp[i][j\dots ]$ precisely, specifying the exact subproblem it models and ensuring it satisfies the Markovian property (past transitions do not affect future options beyond the state variables).
2. Transition Recurrence: Derive a mathematical relation expressing the target state as an aggregate ($\min$, $\max$, or $\sum$) of strictly smaller prerequisite subproblems.
3. Base Cases & Boundaries: Identify trivial edge conditions that terminate the recursion or populate row/column zero of the table.
4. Topological Evaluation Order: Determine loop iteration directions such that whenever computing $dp[\text{state}]$, all required dependent states have already been resolved.

Given $N$ items, each characterized by weight $w_i\in {\mathbb{Z}}^{+}$ and value $v_i\in {\mathbb{Z}}^{+}$, determine the subset of items maximizing total value subject to total weight not exceeding knapsack capacity $W$. Each item can be chosen at most once ($x_i\in \{0,1\}$).

Let $dp[i][w]$ represent the maximum value attainable considering a subset of the first $i$ items with remaining weight capacity $w$, where $0\le i\le N$ and $0\le w\le W$:

Consider $N=3$ items and knapsack capacity $W=5$:

• Item 1: $w_1=1$, $v_1=6$
• Item 2: $w_2=2$, $v_2=10$
• Item 3: $w_3=3$, $v_3=12$

State Matrix $dp[i][w]$:

Step-by-Step State Derivation for Row 3:

• $w=1,2$: $w_3=3>w⟹dp[3][w]=dp[2][w]⟹6,10$.
• $w=3$: $\max (dp[2][3],v_3+dp[2][3-3])=\max (16,12+0)=16$.
• $w=4$: $\max (dp[2][4],v_3+dp[2][4-3])=\max (16,12+6)=18$.
• $w=5$: $\max (dp[2][5],v_3+dp[2][5-3])=\max (16,12+10)=22$.

Optimal Subset Reconstruction

To identify the exact items chosen, backtrack from cell $dp[3][5]=22$:

1. Compare $dp[3][5]$ with $dp[2][5]$ ($22\ne 16$) $⟹$ Item 3 selected. Remaining capacity $=5-3=2$.
2. Compare $dp[2][2]$ with $dp[1][2]$ ($10\ne 6$) $⟹$ Item 2 selected. Remaining capacity $=2-2=0$.
3. Capacity reached $0$. Selected set: {Item 2, Item 3} with total weight $2+3=5$ and maximum value $10+12=22$.

Notice that computing row $i$ relies exclusively on values in row $i-1$. Rows $0\dots i-2$ are never revisited. This observation allows compressing the table from $\Theta (N\cdot W)$ space to a single array of size $W+1$.

When collapsing $dp[i][w]$ into a 1D array $dp[w]$, the capacity iteration order determines problem semantics:

/**
 * Computes the 0/1 Knapsack maximum value using a space-optimized 1D array.
 * Time Complexity:  O(N * W)
 * Space Complexity: O(W)
 */
export function knapsack01SpaceOptimized(
  weights: number[],
  values: number[],
  capacity: number
): number {
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    const wt = weights[i];
    const val = values[i];
    // Traverse backwards to preserve previous-row subproblem solutions
    for (let w = capacity; w >= wt; w--) {
      dp[w] = Math.max(dp[w], val + dp[w - wt]);
    }
  }

  return dp[capacity];
}

Given two sequences $S_1$ of length $m$ and $S_2$ of length $n$, find the length of the longest subsequence present in both. A subsequence preserves relative order without requiring contiguity.

Let $dp[i][j]$ represent the length of the LCS between prefixes $S_1[0\dots i-1]$ and $S_2[0\dots j-1]$:

Dimensions: $(m+1)\times (n+1)=6\times 4$:

Solution Reconstruction

Follow diagonal match arrows ($\nwarrow$):

• $dp[5][3]=3⟹S_1[4]==S_2[2]==\text{’E’}$ $\nwarrow$ move to $(4,2)$.
• $dp[4][2]==dp[3][2]⟹$ move up to $(3,2)$.
• $dp[3][2]=2⟹S_1[2]==S_2[1]==\text{’C’}$ $\nwarrow$ move to $(2,1)$.
• $dp[2][1]==dp[1][1]⟹$ move up to $(1,1)$.
• $dp[1][1]=1⟹S_1[0]==S_2[0]==\text{’A’}$ $\nwarrow$ move to $(0,0)$.

Reconstructed string: "ACE" of length 3.

• 0/1 Knapsack: $\Theta (N\cdot W)$ operations.
  • Pseudo-Polynomial Nature: The capacity $W$ is a numeric input whose binary encoding length is $k=\lceil {\log }_{2}W\rceil$ bits. Relative to the input size in bits, the runtime is $\Theta (N\cdot 2^k)$, which is exponential in the length of $W$. 0/1 Knapsack is weakly NP-complete.
• LCS: $\Theta (m\cdot n)$ operations, which is strictly polynomial in terms of input sequence lengths.

• 2D Tabulation: $\Theta (N\cdot W)$ or $\Theta (m\cdot n)$ auxiliary space.
• Optimized 1D Rolling Buffer: $\Theta (W)$ auxiliary space for Knapsack, or $\Theta (\min (m,n))$ auxiliary space for LCS length computation.

1. Integer Overflow in Minimization Recurrences:

   • In minimization problems such as Coin Change ($dp[w]=\min (dp[w],1+dp[w-c])$), initializing unreachable states to Number.MAX_SAFE_INTEGER causes signed overflow when evaluating $1+dp[w-c]$.
   • Mitigation: Initialize unreachable states to a sentinel upper bound (e.g., $W+1$ or 1e9).

2. Zero-Indexing vs. DP Table Offset:

   • Row $i$ in a $1$-indexed DP table corresponds to item $i-1$ in zero-indexed input arrays weights and values.
   • Mitigation: Standardize on $dp[i]$ representing decisions on the prefix of length $i$, referencing array[i - 1].

3. Direction of Capacity Iteration in 1D Arrays:

   • Forward iteration ($0\to W$) introduces uncontrolled state aliasing, transforming the 0/1 problem into Unbounded Knapsack.
   • Mitigation: Strictly enforce reverse iteration ($W\to w_i$) for single-use item constraints.

4. Continuous State Coordinates:

   • Dynamic programming tables require discrete, integer-addressable states. Continuous domains must be discretized via scaling or solved via alternative techniques such as branch-and-bound or numerical optimization.

• Version Control (git diff): Implements Eugene Myers' $\mathcal{O}(ND)$ diff algorithm, a greedy and dynamic programming exploration of the edit graph between two file versions.
• Relational Query Optimizers: The System R dynamic programming algorithm optimizes multi-table database join orderings in $\mathcal{O}(3^n)$ time compared to the $\mathcal{O}(n!)$ brute force permutation space.
• Speech Recognition & Bioinformatics: The Viterbi algorithm utilizes dynamic programming across Hidden Markov Models (HMMs) to extract the maximum likelihood path of hidden states.

1. Coin Change (LeetCode 322) — Unbounded Knapsack variant with minimization recurrence and sentinel initialization.
2. Partition Equal Subset Sum (LeetCode 416) — Reduction to 0/1 Knapsack with target weight capacity $W=\text{TotalSum}/2$.
3. Edit Distance / Levenshtein Distance (LeetCode 72) — 2D prefix DP handling insertion, deletion, and character replacement costs.
4. Longest Increasing Subsequence (LeetCode 300) — Transitions from $\mathcal{O}(n^2)$ standard tabulation to $\mathcal{O}(n\log n)$ via patience sorting with binary search.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapters 14 & 15. MIT Press.
2. Kleinberg, J., & Tardos, É. (2006). Algorithm Design, Chapter 6: Dynamic Programming. Pearson / Addison-Wesley.
3. Bellman, R. (1957). Dynamic Programming. Princeton University Press.