Dynamic Programming

Dynamic programming (DP) solves problems with optimal substructure (optimal solution built from optimal sub-solutions) and overlapping subproblems (same subproblems recur) by storing results in a table instead of recomputing them.

Two approaches:

• Top-down (memoization) — recurse + cache. Easier to write, computes only needed subproblems
• Bottom-up (tabulation) — fill table iteratively from base cases. No recursion overhead, often more cache-friendly

The pattern:

1. Define the state (what subproblem does $dp[i]$ represent?)
2. Write the recurrence ($dp[i] = f(dp[j], \dots)$ for $j < i$)
3. Identify base cases
4. Determine computation order (dependencies must be solved first)

Critical ML applications:

• Viterbi algorithm — most probable sequence in HMMs / CRFs. $O(T \cdot S^2)$ instead of $O(S^T)$ brute force
• CTC (Connectionist Temporal Classification) — DP over alignment paths for speech recognition
• Beam search — DP-like pruned search over sequences for Autoregressive Generation
• Sequence alignment (Needleman-Wunsch, Smith-Waterman) — foundational in bioinformatics, used in protein language models
• Dynamic Programming in RL — Bellman equations are DP recurrences: $V(s) = \max_a [R + \gamma V(s')]$
• Optimal matrix chain multiplication — choosing the order of matmuls to minimize FLOPs, relevant when chaining large linear layers

Complexity: DP trades space for time. A DP solution is typically $O(\text{states} \times \text{transition cost})$.

See also: Dynamic Programming in RL, Bellman Equations, Graphs and Traversals