python / python-orientation
25 mins
DSA Module 13: 1D & 2D Dynamic Programming
Why This Matters: Dynamic Programming replaces exponential O(2^N) recursive trees with polynomial time state tables.
## Dynamic Programming (Memoization vs Tabulation)
DP optimizes algorithms exhibiting **Overlapping Subproblems** and **Optimal Substructure**.
### Two Approaches
1. **Top-Down (Memoization)**: Recursion + Cache map.
2. **Bottom-Up (Tabulation)**: Iterative state table population.
```python
# 1D Bottom-Up DP: Climbing Stairs
def climb_stairs(n: int) -> int:
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
```
MENTAL MODEL & MEMORY LAYOUT
EXPONENTIAL RECURSION vs DP TABULATION: Exponential O(2^N): fib(5) -> fib(4), fib(3) -> fib(3), fib(2) (Redundant recalculation!) Bottom-Up DP O(N): [0, 1, 1, 2, 3, 5] (Populated linearly in single pass!)
COMMON PITFALLS TO AVOID
- Forgetting base cases `dp[1]=1, dp[2]=2` in tabulation array.
Bottom-Up DP Tabulation
# dp[i] = dp[i-1] + dp[i-2] # Evaluates in O(N) time and O(N) space.
Eliminates redundant recursive subproblems down to linear runtime.
CONCEPT MASTERY CHECKPOINT
What two properties must a problem satisfy to be solvable with Dynamic Programming?
Challenge: Compute total distinct ways to climb N stairs using DP tabulation.