title: "DP Core: Recursion + Memoization" description: "Understand the two cores of DP: recursive decomposition + memoization to avoid repeated calculations. Starting from Fibonacci, master the DP problem-solving framework." order: 1
DP Core: Recursion + Memoization
Starting from Fibonacci
What is Dynamic Programming?
Dynamic Programming (DP) decomposes complex problems into overlapping subproblems, solving each subproblem only once and storing the result for reuse.
| Method | Direction | Memory | Speed | |--------|-----------|--------|-------| | Top-Down (Memoization) | n -> 0 | O(n) call stack | O(n) | | Bottom-Up (Tabulation) | 0 -> n | O(n) array | O(n) |
Three Fibonacci Implementations
from functools import lru_cache
# Recursive version (O(2^n) - super slow)
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2)
print(f"fib_rec(10) = {fib_rec(10)}")
# Method 1: Top-Down Memoization (O(n) - super fast)
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)
print(f"fib_memo(50) = {fib_memo(50)}") # Instant output: 12586269025
# Method 2: Bottom-Up Tabulation
def fib_tab(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp
fib_table = fib_tab(10)
print(f"fib_tab(10) = {fib_table}")
print(f"fib(10) = {fib_table[10]}")
# Method 3: Space Optimized O(1)
def fib_opt(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(f"fib_opt(50) = {fib_opt(50)}")
DP Problem Solving Three Steps
| Step | Question | Fibonacci Example | |------|----------|-------------------| | 1. Define State | What does dp[i] represent? | dp[i] = i-th Fibonacci number | | 2. Recurrence Relation | Relationship between dp[i] and previous? | dp[i] = dp[i-1] + dp[i-2] | | 3. Base Case | What are initial conditions? | dp[0] = 0, dp[1] = 1 |
Applying to Other Problems
Maximum Subarray (Kadane Algorithm): | Step | Kadane | |------|--------| | State | dp[i] = max sum ending at position i | | Recurrence | dp[i] = max(arr[i], dp[i-1] + arr[i]) | | Base | dp[0] = arr[0] |
def max_subarray(arr):
dp = [0] * len(arr)
dp[0] = arr[0]
for i in range(1, len(arr)):
dp[i] = max(arr[i], dp[i-1] + arr[i])
return max(dp)
print(f"Max subarray: {max_subarray([-2,1,-3,4,-1,2,1,-5,4])}") # 6
Time Complexity Comparison
| Problem | Without DP | With DP | Improvement | |---------|-----------|---------|-------------| | Fibonacci(n) | O(2^n) | O(n) | Exponential -> Linear | | Max Subarray(n) | O(n^2) | O(n) | Quadratic -> Linear | | Knapsack(n,W) | O(2^n) | O(nW) | Exponential -> Pseudo-poly | | LCS(n,m) | O(2^(n+m)) | O(nm) | Exponential -> Quadratic |
Summary
| Aspect | Key Point | |--------|-----------| | Memoization | Top-Down recursion + cache | | Tabulation | Bottom-Up iterative array | | State Definition | Most critical step - determines solution direction | | Recurrence Relation | Core formula connecting subproblems | | Base Case | Without it, recursion has no foundation | | Space Optimization | Often can reduce O(n) to O(1) |
Two Key Properties of DP
A problem is solvable with DP if it has two properties:
1. Optimal Substructure
The optimal solution to the big problem can be derived from optimal solutions to smaller subproblems.
- Fibonacci: F(5) = F(4) + F(3)
- Shortest Path: A->C shortest path through B, then A->B and B->C are also shortest
- Longest Path (no cycles): subpaths are not necessarily optimal
2. Overlapping Subproblems
Different decision paths encounter the same subproblems.
- Fibonacci: F(5) needs F(4) and F(3), F(4) also needs F(3)
- Binary Search: each split is a new subproblem, no overlap (Divide & Conquer)
Top-Down vs Bottom-Up
| Method | Style | Advantage | |--------|-------|-----------| | Top-Down (Memoization) | Recursion + cache | Intuitive, only computes needed states | | Bottom-Up (Iterative DP) | For loop + table | No recursion cost, easy space optimization |
When to Use DP
| Problem Characteristic | Check | |-----------------------|-------| | Optimal substructure | Optimal solution contains optimal sub-solutions | | Overlapping subproblems | Same subproblems are solved repeatedly | | Decision at each step | Each step involves choosing between alternatives | | State can be defined | Clear (state, transition, base case) | | Order matters | Sequence of decisions affects the outcome |
If all five are true, DP is likely the right approach.
Summary
Dynamic programming solves problems by breaking them into overlapping subproblems, solving each once, and storing results. Master the five steps: define state, write recurrence, handle base cases, choose top-down or bottom-up, and optimize space.
When to Use DP
Ask these five questions:
- Optimal substructure? Does the optimal solution contain optimal sub-solutions?
- Overlapping subproblems? Are the same sub-solutions solved repeatedly?
- Decision at each step? Does each step involve a choice?
- Definable state? Can you define what (i, j, w, etc.) represents?
- Order matters? Does the sequence of decisions affect the outcome?
If all five are yes, DP is likely the right approach.
Common DP Pitfalls
| Mistake | Fix | |---------|-----| | Wrong state definition | Think carefully about what dimensions you need | | Missing base case | Always define what happens at i=0, j=0, w=0 | | Wrong recurrence | Test on small examples to verify | | Off-by-one errors | Check array indices and loop bounds carefully | | No space optimization | Start with full table, then optimize | | Top-down stack overflow | Python recursion limit ~1000; use bottom-up | | Ignoring order of loops | Wrong loop order produces wrong results |
Practice Problems
| Problem | Key Concept | Difficulty | |---------|-------------|-----------| | Climbing Stairs | Simple 1D DP | Easy | | Fibonacci | 1D DP, O(1) space | Easy | | House Robber | 1D DP with adjacent constraint | Easy | | Jump Game | Greedy/DP for reachability | Medium | | Decode Ways | 1D DP with string parsing | Medium | | Unique Paths | 2D DP grid | Medium | | Minimum Path Sum | 2D DP with min path | Medium |
Key Takeaways
| Concept | Description | |---------|-------------| | State | Defines the subproblem (e.g., dp[i] = min cost to reach i) | | Recurrence | Formula to compute state from smaller states | | Base Case | Simplest subproblem with known answer | | Top-Down | Recursion + memoization (cache) | | Bottom-Up | Iterative table filling | | Space Optimization | Reduce dimensions (2Dโ1DโO(1)) |
Rule of thumb: If you can write a brute-force recursive solution that recomputes the same subproblems, you can convert it to DP. Just add memoization or a table.
What's Next: 0/1 Knapsack
The next chapter applies DP to the classic 0/1 Knapsack problem โ how to define states, fill the DP table, and optimize to a 1D array.