Key Patterns to Master
- 0/1 Knapsack: Picking items with constraints.
- Unbounded Knapsack: Reusing items unlimited times (Coin Change).
- LCS/LIS: Subsequence properties.
- Interval DP: Problems on segments (Palindrome Partitioning).
Hand-Picked Problems
| Problem | Difficulty | Key Pattern |
|---|---|---|
| Climbing Stairs | Easy | Fibonacci DP |
| House Robber | Medium | Pick/Skip |
| 0/1 Knapsack | Medium | Classical DP |
| Longest Increasing Subsequence | Medium | Subsequence |
| Longest Common Subsequence | Medium | 2D Grid DP |
| Coin Change | Medium | Minimum steps |
| Edit Distance | Hard | 2D Transformation |
| Word Break | Medium | Boolean DP |
| Partition Equal Subset Sum | Medium | Sum Targeting |
| Unique Paths | Medium | Grid Combinations |
Interview Tip
Always start by explaining the recursive relation (the $O(2^n)$ way) before jumping into the DP array.