Dynamic Programming
Dynamic Programming
Dynamic programming (DP) solves optimization problems by breaking them into overlapping subproblems, storing solutions (memoization/tabulation). The principle of optimality (Bellman): an optimal solution to a problem contains optimal solutions to its subproblems. DP converts exponential-time naive recursion to polynomial-time computation.
DP & Bellman's Principle
A problem has optimal substructure if an optimal solution is composed of optimal solutions to subproblems. DP approach: (1) characterize optimal subproblem structure; (2) define value function $OPT(i,j,\ldots)$; (3) write Bellman recurrence; (4) compute bottom-up. Time: state space $\times$ transition cost. Memoization (top-down) adds a cache to recursion.
Classic DP Problems
Longest Common Subsequence: $LCS(i,j)=LCS(i-1,j-1)+1$ if $s_i=t_j$, else $\max(LCS(i-1,j),LCS(i,j-1))$. $O(mn)$. Knapsack: $K(i,w)=\max(K(i-1,w), v_i+K(i-1,w-w_i))$. $O(nW)$. Edit distance: $D(i,j)=\min(D(i-1,j)+1, D(i,j-1)+1, D(i-1,j-1)+[s_i\neq t_j])$. Floyd-Warshall: all-pairs shortest paths $d_{ij}^{(k)}=\min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$. $O(n^3)$.
Example 1
Compute $LCS(\text{'ABCBD'},\text{'BCAB'})$.
Solution: DP table ($m=5,n=4$): fill row by row. After filling: $LCS=3$ (e.g., 'BCB' or 'CAB'). The standard DP gives $LCS[5][4]=3$.
Example 2
Solve the 0-1 knapsack: $n=3$ items, $(v,w)=(6,2),(10,4),(12,6)$, capacity $W=8$.
Solution: $K(3,8)=\max(K(2,8),12+K(2,2))$. $K(2,8)=\max(K(1,8),10+K(1,4))=\max(6,10+6)=16$. $K(2,2)=K(1,2)=6$. $K(3,8)=\max(16,12+6)=18$. Take items 1 and 3: value $6+12=18$, weight $2+6=8$. ✓
Practice
- Derive the recurrence for matrix chain multiplication and analyze its $O(n^3)$ complexity.
- Show the Bellman-Ford algorithm as DP: $d_v^{(k)}=\min_{u:(u,v)\in E}(d_u^{(k-1)}+w(u,v))$.
- Design a DP for the rod-cutting problem and prove it gives the optimal solution.
- Describe the Viterbi algorithm for HMMs as a DP and connect it to shortest paths.
Show Answer Key
1. Matrix chain: $m[i,j] = \min_{i\leq k 2. Bellman-Ford DP: $d_v^{(k)} = \min(d_v^{(k-1)}, \min_{u:(u,v)\in E}(d_u^{(k-1)}+w(u,v)))$. $d_v^{(k)}$ = shortest path from source to $v$ using $\leq k$ edges. Base: $d_s^{(0)}=0$, $d_v^{(0)}=\infty$ for $v \neq s$. After $|V|-1$ rounds, all shortest paths found (a shortest path has $\leq |V|-1$ edges). If round $|V|$ still relaxes an edge, a negative cycle exists. 3. Rod-cutting: let $r[j]$ = maximum revenue from a rod of length $j$. $r[j] = \max_{1\leq i\leq j}(p_i + r[j-i])$ where $p_i$ = price of a piece of length $i$. Base: $r[0]=0$. Optimal substructure: an optimal cut of length $j$ consists of a first piece of length $i$ plus an optimal cut of the remaining $j-i$. By induction, this DP gives the optimal solution. $O(n^2)$ time. 4. HMM: states $s_t$, observations $o_t$. Viterbi: $V_t(j) = \max_i [V_{t-1}(i)\cdot a_{ij}]\cdot b_j(o_t)$ where $a_{ij}$ = transition prob, $b_j(o)$ = emission prob. This is DP on a trellis graph: each $(t,j)$ is a node, edges weighted by $\log(a_{ij}b_j(o_t))$. Finding the most likely state sequence = longest (or shortest, with negated log-probs) path in a DAG. $O(TK^2)$ for $K$ states, $T$ time steps.