DP is the most asked topic at FAANG. Master memoization, tabulation, and common DP patterns.
Time
Varies by problem — typically O(n²) or O(n*W)
Space
O(n) to O(n²)
Problems
6 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Climbing Stairs | Easy | Google Amazon Adobe |
| 2 | Longest Increasing Subsequence | Medium | Google Amazon Microsoft |
| 3 | Coin Change | Medium | Amazon Microsoft Goldman Sachs |
| 4 | Longest Common Subsequence | Medium | Google Amazon Meta |
| 5 | Edit Distance | Medium | Google Amazon Microsoft |
| 6 | Regular Expression Matching | Hard | Google Meta Amazon |
Two approaches: Top-down (memoization) and Bottom-up (tabulation)
Identify: optimal substructure + overlapping subproblems
State definition is the hardest part — what do we need to remember?
Space optimization: often can reduce from O(n²) to O(n) using rolling arrays
