Tyler-R-Kendrick Dynamic Programming
Overview
Dynamic programming (DP) is a method for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. Knuth discusses dynamic programming techniques throughout The Art of Computer Programming, particularly in the context of optimization, sequence analysis, and combinatorial problems. The term was coined by Richard Bellman in the 1950s.
Core Principles
Optimal Substructure
A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems. This property allows us to build the global optimum from local optima.
Example: The shortest path from A to C through B consists of the shortest path from A to B plus the shortest path from B to C.
Overlapping Subproblems
A problem has overlapping subproblems when the same subproblems are solved repeatedly in a naive recursive approach. DP eliminates this redundancy by storing results.
Example: Computing Fibonacci(n) recursively recomputes Fibonacci(k) for each k < n exponentially many times.
Two Approaches
Memoization (Top-Down)
Start with the original problem, recurse into subproblems, and cache results as they are computed.
FIB_MEMO(n, cache):
if n <= 1: return n
if n in cache: return cache[n]
cache[n] = FIB_MEMO(n - 1, cache) + FIB_MEMO(n - 2, cache)
return cache[n]
Advantages: Natural to write (follows recursive structure), computes only the subproblems actually needed. Disadvantages: Recursion overhead, potential stack overflow for deep recursion.
Tabulation (Bottom-Up)
Build a table from the smallest subproblems up to the desired result, iterating in a careful order.
FIB_TABLE(n):
if n <= 1: return n
dp[0] = 0, dp[1] = 1
for i = 2 to n:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Advantages: No recursion overhead, easier to optimize space (often only need the last few entries). Disadvantages: May compute subproblems that are never needed, ordering can be less intuitive.
The DP Framework
When facing a potential DP problem, follow these steps:
1. Define the State
Identify what information is needed to describe a subproblem. This becomes the index/key for your DP table.
Example (Knapsack): dp[i][w] = maximum value using items 1..i with capacity w.
2. Write the Recurrence
Express the solution to a subproblem in terms of smaller subproblems.
Example (Knapsack):
dp[i][w] = max(
dp[i-1][w], // skip item i
dp[i-1][w - weight[i]] + value[i] // take item i (if weight[i] <= w)
)
3. Identify the Base Case
Define the values for the smallest subproblems that cannot be decomposed further.
Example (Knapsack): dp[0][w] = 0 for all w (no items means no value).
4. Determine the Build Order
For tabulation, compute subproblems in an order such that all dependencies are resolved before they are needed.
Example (Knapsack): Process items from i = 1 to n, capacities from w = 0 to W.
5. Extract the Answer
The answer to the original problem is at a specific location in the DP table.
Example (Knapsack): dp[n][W].
6. (Optional) Optimize Space
If the recurrence only depends on the previous row or a fixed number of prior entries, reduce the table accordingly.
Example (Fibonacci): Only need dp[i-1] and dp[i-2], so use two variables instead of an array.
Classic Problems
Fibonacci Sequence
| Approach | Time | Space |
|---|---|---|
| Naive recursion | O(2^n) | O(n) stack |
| Memoization | O(n) | O(n) |
| Tabulation | O(n) | O(n) or O(1) optimized |
0/1 Knapsack
Given n items with weights and values, and a knapsack of capacity W, maximize the total value without exceeding the capacity. Each item can be taken at most once.
- State:
dp[i][w]= max value using first i items with capacity w - Recurrence:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]) - Time: O(n * W)
- Space: O(n * W), or O(W) with rolling array
Unbounded Knapsack
Same as 0/1 Knapsack, but each item can be taken unlimited times.
- State:
dp[w]= max value with capacity w - Recurrence:
dp[w] = max(dp[w], dp[w-wt[i]] + val[i])for each item i - Time: O(n * W)
- Space: O(W)
Longest Common Subsequence (LCS)
Find the longest subsequence common to two sequences.
- State:
dp[i][j]= length of LCS of first i characters of X and first j characters of Y - Recurrence:
if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - Time: O(m * n)
- Space: O(m * n), or O(min(m, n)) optimized
Longest Increasing Subsequence (LIS)
Find the length of the longest strictly increasing subsequence.
- State:
dp[i]= length of LIS ending at index i - Recurrence:
dp[i] = max(dp[j] + 1)for all j < i where A[j] < A[i] - Time: O(n^2), or O(n log n) with patience sorting (binary search on tails)
- Space: O(n)
Edit Distance (Levenshtein Distance)
Minimum number of operations (insert, delete, replace) to transform one string into another.
- State:
dp[i][j]= edit distance between first i characters of X and first j characters of Y - Recurrence:
if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], // delete dp[i][j-1], // insert dp[i-1][j-1]) // replace - Time: O(m * n)
- Space: O(m * n), or O(min(m, n)) optimized
Coin Change
Given coin denominations and a target amount, find the minimum number of coins needed (or the number of ways to make change).
Minimum coins:
- State:
dp[a]= minimum coins to make amount a - Recurrence:
dp[a] = min(dp[a - coin] + 1)for each coin denomination - Base case:
dp[0] = 0 - Time: O(amount * number_of_coins)
- Space: O(amount)
Matrix Chain Multiplication
Find the optimal way to parenthesize a sequence of matrices to minimize total scalar multiplications.
- State:
dp[i][j]= minimum cost to multiply matrices i through j - Recurrence:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])for i <= k < j - Base case:
dp[i][i] = 0 - Time: O(n^3)
- Space: O(n^2)
Rod Cutting
Given a rod of length n and prices for each length, find the maximum revenue from cutting the rod.
- State:
dp[l]= maximum revenue for rod of length l - Recurrence:
dp[l] = max(price[k] + dp[l - k])for 1 <= k <= l - Base case:
dp[0] = 0 - Time: O(n^2)
- Space: O(n)
DP Problem Complexity Summary
| Problem | Time | Space |
|---|---|---|
| Fibonacci | O(n) | O(1) optimized |
| 0/1 Knapsack | O(n * W) | O(W) optimized |
| Unbounded Knapsack | O(n * W) | O(W) |
| LCS | O(m * n) | O(min(m, n)) optimized |
| LIS | O(n log n) | O(n) |
| Edit Distance | O(m * n) | O(min(m, n)) optimized |
| Coin Change | O(amount * coins) | O(amount) |
| Matrix Chain Mult. | O(n^3) | O(n^2) |
| Rod Cutting | O(n^2) | O(n) |
Memoization vs Tabulation: When to Use Which
| Factor | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Implementation style | Recursive + cache | Iterative + table |
| Subproblem computation | Only those needed | All subproblems |
| Stack overflow risk | Yes (deep recursion) | No |
| Space optimization | Harder | Easier (rolling arrays) |
| Code clarity | Often more intuitive | Requires careful ordering |
| Performance | Function call overhead | Usually faster in practice |
Guideline: Start with memoization for clarity and correctness, then convert to tabulation if performance or space optimization is needed.
Recognizing DP Problems
A problem is likely solvable with DP if:
- It asks for an optimal value (min, max, count) or the number of ways to achieve something.
- It has overlapping subproblems -- naive recursion recomputes the same states.
- It has optimal substructure -- the optimal solution builds on optimal sub-solutions.
- The problem can be parameterized by a small set of variables (the state space is manageable).
Best Practices
- Always verify optimal substructure before applying DP -- not all optimization problems have it (greedy or exhaustive search may be required instead).
- Define your state precisely and minimally -- extra state dimensions explode the table size.
- Validate your recurrence with small examples before coding.
- Consider whether the problem admits a greedy solution (simpler) before committing to DP.
- For interview/competition settings, practice identifying the state and recurrence quickly -- the implementation follows mechanically.
- Reference Knuth's TAOCP for mathematical rigor on sequence problems, optimal search trees, and combinatorial optimization where DP techniques apply.