1-D Dynamic Programming

Overview

Dynamic programming is about (a) defining a state that captures the subproblem, (b) writing a recurrence between states, and (c) choosing between top-down memoization and bottom-up tabulation. The 1-D category is where you build the reflex:

• Top-down (memo): natural recursion + cache. Write the recursion first; add @lru_cache; done.
• Bottom-up (tabulation): iterative, usually cleaner once you trust the recurrence. Often admits space optimization from $O(n)$ to $O(1)$.
• Space optimization: if dp[i] only depends on dp[i-1], dp[i-2], …, keep a sliding window.

Problems

1. 70. Climbing Stairs (Easy)
2. 746. Min Cost Climbing Stairs (Easy)
3. 198. House Robber (Medium)
4. 213. House Robber II (Medium)
5. 5. Longest Palindromic Substring (Medium)
6. 647. Palindromic Substrings (Medium)
7. 91. Decode Ways (Medium)
8. 322. Coin Change (Medium)
9. 152. Maximum Product Subarray (Medium)
10. 139. Word Break (Medium)
11. 300. Longest Increasing Subsequence (Medium)
12. 416. Partition Equal Subset Sum (Medium)

Key patterns unlocked here

• Fibonacci recurrence: Climbing Stairs, Min Cost Climbing Stairs.
• Take-or-skip DP: House Robber (+ circular variant).
• Expand around center / DP table: Palindromic Substrings.
• Carry-two-states: Maximum Product Subarray (track max AND min).
• Unbounded knapsack: Coin Change.
• 0/1 knapsack: Partition Equal Subset Sum.
• LIS via DP or patience sort: Longest Increasing Subsequence.
• Index DP on strings: Decode Ways, Word Break.