DP Practice Questions
Ten interview classics. Each one is a direct application of one of the seven classic patterns or an advanced technique — once you spot the pattern, the state writes itself.
Before reading any solution, force yourself through the state-design checklist:
- What am I computing? (English sentence)
- What are the dimensions of the state?
- What are the base cases?
- What’s the transition?
- What order do I fill the table?
The code is a 10-line transcription of those five answers. If you can answer them, you’ve solved the problem.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Climbing Stairs | 1D linear (Fibonacci-shaped) | Available |
| House Robber | 1D linear (skip/take) | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Coin Change | Unbounded knapsack (min) | Available |
| Longest Increasing Subsequence | LIS — O(n²) and O(n log n) | Available |
| Longest Common Subsequence | 2D string DP | Available |
| 0/1 Knapsack | Subset selection with weight limit | Available |
| Partition Equal Subset Sum | Subset sum (knapsack reduction) | Available |
| Word Break | Unbounded knapsack on strings | Available |
| Maximum Product Subarray | Kadane variant — track min and max | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Edit Distance | 2D string DP — replace / insert / delete | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Unique Paths II | Grid DP with obstacles | Coming Soon |
| Decode Ways | 1D linear with conditional transitions | Coming Soon |
| House Robber II | Linear DP on a circular array | Coming Soon |
| Coin Change II | Unbounded knapsack (count of ways) | Coming Soon |
| Distinct Subsequences | LCS variant — count, not length | Coming Soon |
| Burst Balloons | Interval DP | Coming Soon |
| Palindrome Partitioning II | Min cuts via DP | Coming Soon |
| Best Time to Buy and Sell Stock IV | Stock DP with state (day, txn, hold) | Coming Soon |
| Regular Expression Matching | 2D DP with * and . | Coming Soon |
| Travelling Salesman (Held–Karp) | Bitmask DP | Coming Soon |