Dynamic Programming
Dynamic Programming (DP) is a powerful problem-solving technique commonly applied to optimization problems (find the minimum cost or maximum value), counting problems (how many ways can something be done?), and existence problems (is a solution even possible?). It works by breaking a complex problem into overlapping subproblems, solving each one exactly once, and storing the results to avoid redundant computation. Think of it as "smart recursion" — remembering what you've already calculated so you never repeat the same work.
What Is Dynamic Programming?#
Dynamic programming solves problems by combining solutions to subproblems. Unlike divide-and-conquer (which splits a problem into independent subproblems that share no work), DP is designed for problems where subproblems overlap — the same calculation appears repeatedly at different points in the recursion. Without memoization or tabulation, a naive recursive solution would recompute the same results exponentially many times.
Real-World Analogies#
- Climbing Stairs: Instead of counting every possible path from scratch, remember how many ways to reach each step
- GPS Navigation: Calculate shortest paths to intermediate points, then combine them for the full route
- Financial Planning: Compute optimal decisions for each year, building on previous years' calculations
- Game Strategy: Store winning/losing positions so you don't re-analyze the same board state
Key Characteristics#
| Property | Description |
|---|---|
| Overlapping Subproblems | The same subproblem appears multiple times during recursion |
| Optimal Substructure | An optimal solution contains optimal solutions to its subproblems |
| Memoization | Top-down approach: cache results of recursive calls |
| Tabulation | Bottom-up approach: fill a table iteratively from base cases |
| Space-Time Trade-off | Uses extra space (O(n) or O(n²)) to save time (often exponential → polynomial) |
The Problem: Overlapping Subproblems#
Consider computing the 5th Fibonacci number using naive recursion. Notice how fib(2) and fib(3) are calculated multiple times:
The red nodes show duplicate calculations. With naive recursion, fib(n) takes O(2ⁿ) time because we recalculate the same values exponentially many times.
Dynamic Programming fixes this by computing each subproblem only once and storing the result.
Two Approaches: Top-Down vs Bottom-Up#
Top-Down (Memoization)#
Start from the main problem and recursively solve subproblems. Store results in a cache (memo) so each subproblem is solved only once.
Bottom-Up (Tabulation)#
Start from base cases and iteratively build up to the main problem. Fill a table from small subproblems to large.
Comparison#
| Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Direction | Starts from main problem, goes down | Starts from base cases, builds up |
| Implementation | Recursive with cache | Iterative with array/table |
| Subproblems Solved | Only needed ones (lazy) | All subproblems (eager) |
| Stack Usage | Uses call stack (recursion depth) | No recursion, constant stack |
| Ease of Writing | Often more intuitive | Requires understanding order |
| Space Optimization | Harder to optimize | Easier to reduce space |
Fibonacci Sequence#
The classic introduction to DP. Let's see how DP transforms exponential time complexity to linear.
Fibonacci Number
Compute the nth Fibonacci number using dynamic programming
Climbing Stairs#
Problem: You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?
Key Insight#
To reach step n, you either came from step n-1 (by taking 1 step) or from step n-2 (by taking 2 steps). So the number of distinct ways to reach step n is:
dp[n] = dp[n-1] + dp[n-2]
The base cases are:
dp[0] = 1: there is exactly 1 way to be at the starting position — do nothing. This acts as the "seed" that all other counts build on.dp[1] = 1: there is exactly 1 way to reach step 1 — take a single 1-step.
This is exactly the Fibonacci recurrence! Climbing stairs is Fibonacci in disguise.
Climbing Stairs
Count ways to climb n stairs taking 1 or 2 steps at a time
Coin Change#
Problem: Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. You have unlimited coins of each denomination.
Key Insight#
For each amount i, try every coin c. If we can make amount i-c with k coins, then we can make i with k+1 coins:
dp[i] = min(dp[i], dp[i - coin] + 1) for each coin
Coin Change
Find minimum coins needed to make a target amount
Longest Common Subsequence (LCS)#
Problem: Given two strings, find the length of their longest common subsequence. A subsequence is derived from a string by deleting zero or more characters without changing the order of the remaining characters. A common subsequence of two strings is a subsequence that appears in both. For example, "ACE" is a subsequence of "ABCDE" (delete B and D), so if "ACE" also appears as a subsequence of the second string, it is a common subsequence.
Key Insight#
Compare characters at each position:
- If
s1[i] == s2[j]: extend the LCS by 1 →dp[i][j] = dp[i-1][j-1] + 1 - If different: take the max of skipping either character →
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Longest Common Subsequence
Find the length of the longest common subsequence of two strings
0-1 Knapsack#
Problem: You have a knapsack with capacity W and n items, each with weight and value. Maximize the total value without exceeding capacity. Each item can only be taken once (0 or 1 times).
Key Insight#
For each item i at each capacity w, we have two choices:
- Don't take it: Keep the best value achievable using only the previous items →
dp[i][w] = dp[i-1][w] - Take it (if it fits): Use the remaining capacity with only the previous items, then add this item's value →
dp[i][w] = dp[i-1][w - weight[i]] + value[i]
We take the maximum of both choices. Notice that both cases reference dp[i-1] (the row before item i was considered). This is what enforces the "0 or 1" constraint: we only ever look at prior decisions, so the same item cannot be counted twice.
0-1 Knapsack
Maximize value in knapsack without exceeding capacity
Common DP Patterns#
Pattern 1: Linear DP (1D)#
Single sequence problems where dp[i] depends on previous elements.
| Problem | State | Transition |
|---|---|---|
| Fibonacci | dp[i] = ith Fibonacci | dp[i] = dp[i-1] + dp[i-2] |
| Climbing Stairs | dp[i] = ways to reach step i | dp[i] = dp[i-1] + dp[i-2] |
| House Robber | dp[i] = max money from first i houses | dp[i] = max(dp[i-1], dp[i-2] + nums[i]) |
| Max Subarray | dp[i] = max sum ending at i | dp[i] = max(nums[i], dp[i-1] + nums[i]) |
Pattern 2: Grid DP (2D)#
Problems on grids where dp[i][j] depends on adjacent cells.
| Problem | State | Transition |
|---|---|---|
| Unique Paths | dp[i][j] = paths to (i,j) | dp[i][j] = dp[i-1][j] + dp[i][j-1] |
| Min Path Sum | dp[i][j] = min cost to (i,j) | dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) |
| Edit Distance | dp[i][j] = edits for s1[:i] → s2[:j] | Match: dp[i-1][j-1], Insert/Delete/Replace |
Pattern 3: Two-Sequence DP#
Problems comparing or combining two sequences.
| Problem | State | Transition |
|---|---|---|
| LCS | dp[i][j] = LCS length for s1[:i], s2[:j] | Match: dp[i-1][j-1]+1, Else: max(skip either) |
| Edit Distance | dp[i][j] = min edits | Match: dp[i-1][j-1], Else: 1+min(insert,delete,replace) |
| Interleaving String | dp[i][j] = can form s3[:i+j]? | Match s1[i] or s2[j] to s3[i+j] |
Pattern 4: Knapsack / Subset#
Problems involving selecting items with constraints.
| Variant | Description | Loop Direction |
|---|---|---|
| 0-1 Knapsack | Each item used at most once | Backwards (right to left) |
| Unbounded Knapsack | Unlimited copies of each item | Forwards (left to right) |
| Subset Sum | Can we make target sum? | Same as 0-1 Knapsack |
| Coin Change | Min coins for amount | Unbounded variant |
How to Approach DP Problems#
Step 1: Identify if It's a DP Problem#
Look for these clues:
- Optimization: Find min/max, longest/shortest, count ways
- Overlapping subproblems: Same calculations needed multiple times
- Choices: At each step, you make a decision (take/skip, left/right)
- Sequential decisions: Current choice affects future options
Step 2: Define the State#
Ask: "What information do I need to solve subproblems?"
| Problem Type | State Usually Looks Like |
|---|---|
| Linear sequence | dp[i] = answer for first i elements |
| Two sequences | dp[i][j] = answer for s1[:i] and s2[:j] |
| Grid | dp[i][j] = answer at position (i, j) |
| Knapsack | dp[i][w] = answer using first i items with capacity w |
| Interval | dp[i][j] = answer for range [i, j] |
Step 3: Find the Transition#
Ask: "How does the current state relate to previous states?"
Think about:
- What choices can I make at this step?
- How do those choices connect to smaller subproblems?
- What's the recurrence relation?
Step 4: Identify Base Cases#
What are the simplest subproblems with known answers?
- Empty sequence:
dp[0] = 0ordp[0] = 1 - Single element:
dp[1] = ... - First row/column of grid: Often initialized separately
Step 5: Determine Order of Computation#
For bottom-up DP: solve subproblems in an order where dependencies are computed first.
- Usually left-to-right, top-to-bottom
- For 0-1 Knapsack with 1D array: right-to-left
Reviewing AI-Generated Code#
Understanding dynamic programming helps you evaluate AI-generated solutions.
What to Verify#
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Base Cases | All base cases defined and correct | Missing or wrong base case leads to wrong results |
| State Definition | State captures all needed information | Incomplete state misses subproblem distinctions |
| Transition Logic | Recurrence relation is mathematically correct | Off-by-one errors in indices |
| Initialization | DP array initialized to correct values | Using 0 when should be infinity or vice versa |
| Loop Order | Each subproblem is solved after all its dependencies | Iterating in the wrong direction — e.g., using a forward loop in 1D knapsack allows the same item to be picked multiple times |
Common AI Pitfalls#
Dynamic Programming Bugs
Common mistakes AI makes in DP implementations
Questions to Ask AI#
When AI generates DP code, verify:
- "What does dp[i] represent exactly?"
- "What are the base cases and why?"
- "Can you prove the recurrence relation is correct?"
- "Is memoization or tabulation more appropriate here?"
Summary#
| Concept | Key Takeaway |
|---|---|
| Dynamic Programming | Break into subproblems, solve once, store results |
| Overlapping Subproblems | Same subproblem appears multiple times |
| Optimal Substructure | Optimal solution contains optimal sub-solutions |
| Memoization (Top-Down) | Recursive + cache, solves only needed subproblems |
| Tabulation (Bottom-Up) | Iterative, fills table from base cases |
| State Definition | Most critical step — what info defines a subproblem? |
| Transition | How current state relates to previous states |
Complexity Improvements with DP#
| Problem | Brute Force | With DP |
|---|---|---|
| Fibonacci | O(2ⁿ) | O(n) |
| Coin Change | Exponential | O(amount × n) |
| LCS | O(2⁽ᵐ⁺ⁿ⁾) | O(m × n) |
| 0-1 Knapsack | O(2ⁿ) | O(n × W) |
Dynamic programming transforms exponential-time problems into polynomial-time solutions by remembering what you've already computed. Master the patterns, practice state definitions, and you'll recognize DP opportunities everywhere!