Dynamic Programming
3 programs — patterns, complexity, and code
| # | Program Name | Pattern | Time | Space | Key Idea | Level |
|---|---|---|---|---|---|---|
| 1 | climbingStairs | DP (Fibonacci) | O(n) | O(1) | Ways to reach step n = ways(n-1) + ways(n-2); same recurrence as Fibonacci. | Simple |
| 2 | houseRobber | DP (linear) | O(n) | O(1) | At each house decide: rob it (prev_prev + curr) or skip (prev). Take the max. | Simple |
| 3 | coinChange | DP (BFS / bottom-up) | O(amount·n) | O(amount) | dp[i] = min coins to make amount i; try every coin and take the minimum. | Middle |