10.6 Dynamic programming

Fundamentals of Dynamic Programming

Dynamic programming (DP) solves complex problems by breaking them into smaller subproblems, solving each one just once, and storing the results for reuse. This avoids the massive redundancy you'd get from a naive recursive approach. Two properties must hold for DP to work: optimal substructure and overlapping subproblems.

Optimal Substructure Principle

A problem has optimal substructure when its best solution can be built from the best solutions of its subproblems. Think of finding the shortest path from A to C through B: if the overall shortest path goes through B, then the A-to-B portion must itself be the shortest path from A to B. If it weren't, you could swap in a shorter one and improve the whole route.

This property lets you write a recursive formula for the optimal solution, and it's what makes DP work at all. Without it, solving subproblems optimally wouldn't guarantee a globally optimal answer.

Overlapping Subproblems Property

Overlapping subproblems means the same subproblems come up again and again during recursion. The Fibonacci sequence is the classic example: computing $F(5)$ requires $F(4)$ and $F(3)$, but computing $F(4)$ also requires $F(3)$. Without DP, you'd recompute $F(3)$ (and many others) multiple times.

When subproblems overlap, you can store each result the first time you compute it and just look it up afterward. This is what transforms an exponential algorithm into a polynomial one.

Memoization vs Tabulation

These are the two main strategies for implementing DP:

• Memoization (top-down): You write a recursive solution, but add a cache (usually a dictionary or array). Before computing a subproblem, check if the answer is already stored. If so, return it immediately. This approach only solves the subproblems you actually need.
• Tabulation (bottom-up): You fill in a table starting from the smallest subproblems and work your way up. No recursion involved. You iterate through all subproblems in a logical order so that by the time you need a value, it's already been computed.

Both eliminate redundant computation. Memoization can be easier to write since it mirrors the recursive structure, but tabulation avoids recursion overhead and the risk of stack overflow on large inputs.

Problem-Solving Approach

Solving a DP problem follows a consistent pattern. The challenge is usually in steps 1 and 2:

1. Define the state — what information do you need to describe a subproblem?
2. Write the state transition equation — how does the solution to a subproblem relate to smaller subproblems?
3. Identify the base cases — what are the smallest subproblems you can solve directly?
4. Decide on memoization or tabulation — top-down or bottom-up?
5. Trace through a small example to verify correctness before coding.

Top-Down vs Bottom-Up Methods

• Top-down starts with the original problem and recursively breaks it apart. You add memoization so each subproblem is solved at most once. This is natural when the recursive structure is obvious.
• Bottom-up starts with the base cases and builds toward the final answer iteratively, filling a table row by row (or cell by cell). This avoids recursion entirely.

The choice often comes down to the problem. Top-down can be simpler to think about; bottom-up tends to be faster in practice and easier to optimize for space.

Recursive vs Iterative Implementations

Recursive implementations map directly onto the top-down approach. They're often more intuitive because they mirror how you'd describe the problem mathematically. The downside: deep recursion can cause stack overflow for large inputs.

Iterative implementations go with bottom-up tabulation. They generally use less memory (no call stack) and can be easier to optimize. Converting from recursive to iterative sometimes requires an explicit stack data structure, though for many DP problems the tabulation order is straightforward.

State Transition Equations

The state transition equation (or recurrence relation) is the heart of any DP solution. It defines mathematically how the answer to a larger subproblem depends on smaller ones.

For example, the Fibonacci recurrence is simply $F(n) = F(n-1) + F(n-2)$. For more complex problems, deriving this equation requires careful analysis of what choices are available at each step and how those choices affect the remaining subproblem.

Getting this equation right is the hardest part of DP. Once you have it, implementation is mostly mechanical.

Common Dynamic Programming Patterns

0/1 Knapsack Problem

You have $n$ items, each with a weight and a value, and a knapsack that holds at most $W$ weight. The goal: maximize total value without exceeding the weight limit. Each item is either taken or left (no fractions).

State: $dp[i][w]$ = maximum value using the first $i$ items with weight capacity $w$.

Transition:

$dp[i][w] = \max(dp[i-1][w],\ dp[i-1][w - weight[i]] + value[i])$

The first option skips item $i$; the second takes it (only valid if $weight[i] \leq w$).

Time complexity: $O(nW)$. This applies to resource allocation, budgeting, and any scenario where you're choosing from a set of options with constraints.

Longest Common Subsequence

Given two sequences, find the longest subsequence present in both (characters don't need to be consecutive, but their order must be preserved).

State: $dp[i][j]$ = length of the longest common subsequence of the first $i$ characters of sequence A and the first $j$ characters of sequence B.

Transition:

• If $A[i] = B[j]$: $dp[i][j] = dp[i-1][j-1] + 1$
• Otherwise: $dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1])$

Time complexity: $O(mn)$ for sequences of length $m$ and $n$. Applications include DNA sequence alignment and diff tools in version control.

Matrix Chain Multiplication

Given a chain of matrices, determine the parenthesization that minimizes the total number of scalar multiplications. Matrix multiplication is associative, so the result is the same regardless of order, but the computational cost varies dramatically.

State: $dp[i][j]$ = minimum cost to multiply matrices $i$ through $j$.

Transition:

$dp[i][j] = \min_{i \leq k < j}(dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j)$

where $p$ is the array of matrix dimensions.

Time complexity: $O(n^3)$ for $n$ matrices.

Time and Space Complexity

Optimizing Memory Usage

Many DP solutions use a 2D table, but you can often reduce space if each row only depends on the previous row:

• Rolling arrays: Keep only two rows (current and previous) instead of the full table. This drops space from $O(n \cdot W)$ to $O(W)$ in problems like the knapsack.
• Single-row optimization: For some problems, you can even fill a single row in the right order (usually right-to-left for 0/1 knapsack) to avoid overwriting values you still need.
• State compression: When the state involves subsets of a small set, represent each subset as a bitmask (an integer), which is compact and allows fast bitwise operations.

Trade-offs Between Time and Space

Sometimes you can save memory by not storing intermediate results and recomputing them when needed. This trades time for space. The right balance depends on:

• The size of the input (large inputs may exhaust memory before time)
• Hardware constraints (embedded systems vs. servers)
• Whether the problem's dependency structure allows rolling-array tricks

In general, DP already trades space for time (by storing subproblem results). The optimization question is how much of that stored data you actually need at any given point.

Applications in Mathematics

Fibonacci Sequence Optimization

The naive recursive Fibonacci has $O(2^n)$ time complexity because it recomputes the same values exponentially many times. DP fixes this:

1. Memoized recursion: Store each $F(k)$ after computing it. Time: $O(n)$, space: $O(n)$.
2. Tabulation: Fill an array from $F(0)$ up to $F(n)$. Time: $O(n)$, space: $O(n)$.
3. Space-optimized: Since $F(n)$ only depends on the two previous values, keep just two variables. Time: $O(n)$, space: $O(1)$.
4. Matrix exponentiation: Represent the recurrence as a matrix and use fast exponentiation. Time: $O(\log n)$.

This progression from $O(2^n)$ down to $O(\log n)$ is a great illustration of how DP thinking leads to increasingly efficient solutions.

Catalan Numbers Computation

Catalan numbers count many combinatorial structures: the number of valid arrangements of $n$ pairs of parentheses, the number of distinct binary search trees with $n$ nodes, and more.

The recurrence relation is:

$C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}, \quad C_0 = 1$

A DP table computes this in $O(n^2)$ time and $O(n)$ space by filling in $C_0, C_1, \ldots, C_n$ in order, since each $C_n$ depends on all previous values.

Binomial Coefficient Calculation

The binomial coefficient $\binom{n}{k}$ counts the number of ways to choose $k$ items from $n$. Pascal's triangle gives the recurrence:

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

A naive recursive approach recomputes many values. DP tabulation fills in Pascal's triangle row by row. With a space optimization (using a single array of length $k+1$ updated right-to-left), you get $O(nk)$ time and $O(k)$ space. This is far more efficient and numerically stable than computing factorials directly.

Advanced Dynamic Programming Techniques

Bitmasking in Dynamic Programming

When a problem involves choosing subsets of a small set (typically $n \leq 20$), you can represent each subset as a binary number. Bit $i$ being 1 means element $i$ is included.

• The state becomes an integer (the bitmask), so your DP table is an array indexed by integers from $0$ to $2^n - 1$.
• State transitions use bitwise operations: checking membership with mask & (1 << i), adding an element with mask | (1 << i).
• This is used in the Traveling Salesman Problem (Held-Karp algorithm) and assignment problems.

The constraint $n \leq 20$ matters because $2^{20} \approx 10^6$, which is manageable. Beyond that, the exponential blowup makes this impractical.

Divide and Conquer Optimization

This technique applies when the DP transition has a special monotonicity property: the optimal "split point" for row $i$ is non-decreasing as you move across columns. When this holds (often provable via the quadrangle inequality), you can use divide and conquer to find optimal split points more efficiently.

• Reduces $O(n^3)$ to $O(n^2 \log n)$ in many cases.
• Applies to problems like the optimal binary search tree and certain partitioning problems.

Convex Hull Optimization

When the DP transition can be written as choosing the minimum (or maximum) over a set of linear functions, you can maintain a convex hull of those functions. Each transition then reduces to a query on the hull rather than scanning all previous states.

This turns an $O(n^2)$ DP into $O(n \log n)$ or even $O(n)$ if queries are monotone. It requires comfort with computational geometry concepts but provides significant speedups for the right class of problems.

Dynamic Programming in Graph Theory

Shortest Path Algorithms

Two classic shortest-path algorithms are built on DP:

• Bellman-Ford: Finds shortest paths from a single source by relaxing all edges $V - 1$ times. Time: $O(VE)$. Handles negative edge weights (and detects negative cycles).
• Floyd-Warshall: Finds shortest paths between all pairs of vertices. Uses a 3D DP (often compressed to 2D) where $dp[i][j]$ is updated by considering each vertex $k$ as a potential intermediate node. Time: $O(V^3)$.

Both work because shortest paths have optimal substructure: a shortest path from A to C through B contains the shortest path from A to B. Dijkstra's algorithm, by contrast, is greedy and cannot handle negative edge weights.

Traveling Salesman Problem

The Held-Karp algorithm solves TSP exactly using DP with bitmasks:

• State: $dp[S][v]$ = minimum cost to visit all cities in set $S$, ending at city $v$.
• Transition: Try extending from each possible previous city in $S$.
• Time: $O(n^2 \cdot 2^n)$, a huge improvement over the brute-force $O(n!)$.

For $n = 20$, this is roughly $4 \times 10^8$ operations (feasible) versus $2.4 \times 10^{18}$ for brute force (not feasible).

Minimum Spanning Tree Variants

Standard MST algorithms (Kruskal's, Prim's) are greedy. However, constrained variants like the $k$-MST problem (find the minimum-weight subtree spanning exactly $k$ vertices) don't have the greedy property and require DP approaches.

These variants arise in network design and clustering, where you need a tree connecting a specific number of nodes rather than all of them.

Limitations and Alternatives

NP-Hard Problems

DP doesn't magically make all problems efficient. For NP-hard problems, the state space is typically exponential, so even with DP, the solution isn't polynomial-time. The Traveling Salesman Problem is a good example: DP gives $O(n^2 \cdot 2^n)$, which is much better than $O(n!)$ but still exponential.

Problems like graph coloring and boolean satisfiability (SAT) fall into this category. For these, exact DP solutions are only practical for small inputs.

Approximation Algorithms

When exact solutions are too slow, approximation algorithms find near-optimal answers with guaranteed quality bounds. For example, the FPTAS (Fully Polynomial-Time Approximation Scheme) for the knapsack problem uses DP on a scaled-down version of the problem to get a $(1 - \epsilon)$-optimal solution in polynomial time.

The key idea: you trade a small, controlled loss in solution quality for a large gain in speed.

Greedy Algorithms vs Dynamic Programming

Greedy algorithms make the locally best choice at each step and never look back. They're simpler and faster than DP, but they only give optimal solutions when the problem has the greedy choice property (making a locally optimal choice doesn't prevent reaching a globally optimal solution).

• Greedy works: activity selection, Huffman coding, MST (Kruskal's/Prim's)
• Greedy fails, DP needed: 0/1 knapsack, longest common subsequence, matrix chain multiplication

The test: if you can prove that a greedy choice is always safe (often via matroid theory), use greedy. Otherwise, you likely need DP.