Ask a room of candidates which topic they’d remove from FAANG interviews if they could, and dynamic programming wins by a landslide. It feels like an endless sea of unrelated puzzles (climbing stairs one day, burst balloons the next) with no visible connection between them.
Here’s the secret that experienced candidates eventually discover: there is no sea. There are about ten ponds. Nearly every DP question asked at Google, Meta, Amazon, and friends is a variation on a small set of recurring patterns. Learn the patterns and you stop solving individual problems; you start recognizing which pond you’re standing in and applying the recurrence you already know.
This post catalogs the ten patterns, each with an explanation, a Python example, and the canonical LeetCode problem to practice. If DP is completely new to you, read Day 30: Dynamic Programming Introduction first. This post assumes you know what memoization and tabulation are.
Why FAANG Tests DP So Heavily
Before the patterns, it’s worth understanding why interviewers love DP, because it explains what they’re grading:
- DP resists memorization. A candidate who memorized Two Sum can regurgitate it. A DP problem with one twist forces you to re-derive the recurrence live, which is exactly the reasoning signal interviewers want.
- It layers multiple skills. A single DP problem tests recursion, state design, complexity analysis, and optimization (top-down to bottom-up, then space reduction), which is a lot of signal per 45 minutes.
- It has a clean difficulty dial. Interviewers can start with the base problem and add follow-ups (“now return the actual subsequence,” “now do it in O(n) space”) to calibrate levels.
The grading rubric is almost always the same: define the state, state the recurrence, identify base cases, analyze complexity. Every pattern below is organized around those four steps.
Pattern 1: 1D DP (Fibonacci-Style)
The shape: the answer for position i depends on a fixed number of previous positions.
State: dp[i] = best answer considering the first i elements. Recurrence: dp[i] = f(dp[i-1], dp[i-2], ...).
The classic is House Robber (LeetCode 198): rob houses for maximum money, but never two adjacent houses.
1def rob(nums):
2 prev2, prev1 = 0, 0
3 for num in nums:
4 # Either skip this house, or rob it + best from two back
5 prev2, prev1 = prev1, max(prev1, prev2 + num)
6 return prev1
Notice we never built an array: when dp[i] only needs the last two values, two variables suffice. Mentioning that space optimization unprompted is an easy senior-signal in interviews. The full derivation from naive recursion to O(1) space is walked through in Day 31: Fibonacci and DP.
Practice: Climbing Stairs (70), House Robber (198), Decode Ways (91).
Pattern 2: 0/1 Knapsack
The shape: items with weights and values, a capacity, and each item used at most once. Maximize value.
State: dp[i][w] = best value using the first i items with capacity w. Recurrence: take it or leave it.
1def knapsack(weights, values, capacity):
2 dp = [0] * (capacity + 1)
3 for i in range(len(weights)):
4 # Iterate capacity DOWNWARD so each item is used once
5 for w in range(capacity, weights[i] - 1, -1):
6 dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
7 return dp[capacity]
The downward capacity loop is the entire trick of the 1D-compressed version. Iterate upward and you accidentally allow reuse (which turns this into Pattern 3). Interviewers ask about this distinction constantly. Day 33: The Knapsack Problem covers the 2D version and the compression step by step.
Practice: Partition Equal Subset Sum (416), Target Sum (494), Last Stone Weight II (1049). Note that many knapsack interview problems disguise the “capacity” as a target sum.
Pattern 3: Unbounded Knapsack (Coin Change)
The shape: same as knapsack, but items can be reused unlimited times.
Coin Change (LeetCode 322) is the canonical version: fewest coins to make an amount.
1def coin_change(coins, amount):
2 dp = [float('inf')] * (amount + 1)
3 dp[0] = 0
4 for coin in coins:
5 for amt in range(coin, amount + 1): # upward = reuse allowed
6 dp[amt] = min(dp[amt], dp[amt - coin] + 1)
7 return dp[amount] if dp[amount] != float('inf') else -1
Compare the loop direction with Pattern 2: that single difference is the whole distinction between the two patterns. Day 37: The Coin Change Problem and Day 38: Rod Cutting are both unbounded knapsack in different costumes.
Practice: Coin Change (322), Coin Change II (518), Perfect Squares (279).
Pattern 4: Longest Common Subsequence (Two-Sequence DP)
The shape: two sequences, and you’re comparing, aligning, or matching them.
State: dp[i][j] = answer for the first i characters of one string and the first j of the other.
1def lcs(text1, text2):
2 m, n = len(text1), len(text2)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 for i in range(1, m + 1):
5 for j in range(1, n + 1):
6 if text1[i-1] == text2[j-1]:
7 dp[i][j] = dp[i-1][j-1] + 1
8 else:
9 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
10 return dp[m][n]
The two-branch structure (“characters match: extend the diagonal; don’t match: take the better of dropping one character from either side”) reappears in a dozen problems. Full walkthrough in Day 32: Longest Common Subsequence.
Practice: Longest Common Subsequence (1143), Delete Operation for Two Strings (583), Distinct Subsequences (115).
Pattern 5: Longest Increasing Subsequence
The shape: find the longest subsequence of one array satisfying an ordering property.
1def length_of_lis(nums):
2 dp = [1] * len(nums) # dp[i] = LIS ending exactly at i
3 for i in range(len(nums)):
4 for j in range(i):
5 if nums[j] < nums[i]:
6 dp[i] = max(dp[i], dp[j] + 1)
7 return max(dp) if nums else 0
This is O(n²); the follow-up interviewers love is the O(n log n) version using binary search on a “tails” array, which connects to the boundary-finding template from Binary Search: Not Just for Sorted Arrays. Derivation and both versions are in Day 35: Longest Increasing Subsequence.
Practice: Longest Increasing Subsequence (300), Russian Doll Envelopes (354), Maximum Length of Pair Chain (646).
Pattern 6: Edit Distance (String Transformation)
The shape: transform one string into another with insert/delete/replace operations, minimizing cost.
1def min_distance(word1, word2):
2 m, n = len(word1), len(word2)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 for i in range(m + 1):
5 dp[i][0] = i # delete everything
6 for j in range(n + 1):
7 dp[0][j] = j # insert everything
8 for i in range(1, m + 1):
9 for j in range(1, n + 1):
10 if word1[i-1] == word2[j-1]:
11 dp[i][j] = dp[i-1][j-1]
12 else:
13 dp[i][j] = 1 + min(dp[i-1][j-1], # replace
14 dp[i-1][j], # delete
15 dp[i][j-1]) # insert
16 return dp[m][n]
Structurally this is LCS with a third branch and non-trivial base cases. If you can explain why each of the three min arguments corresponds to an edit operation, you understand the pattern; if you can’t, you memorized it. Day 36: Edit Distance builds that explanation carefully.
Practice: Edit Distance (72), One Edit Distance (161), Regular Expression Matching (10) for the brave.
Pattern 7: Interval DP
The shape: the answer for a range [i, j] is built from answers of sub-ranges, and you typically iterate by interval length.
Matrix Chain Multiplication is the textbook example (Day 34); Burst Balloons (LeetCode 312) is the interview favorite:
1def max_coins(nums):
2 balloons = [1] + nums + [1]
3 n = len(balloons)
4 dp = [[0] * n for _ in range(n)]
5 for length in range(2, n): # interval length
6 for left in range(n - length):
7 right = left + length
8 for k in range(left + 1, right): # k = LAST balloon popped
9 dp[left][right] = max(
10 dp[left][right],
11 dp[left][k] + dp[k][right]
12 + balloons[left] * balloons[k] * balloons[right]
13 )
14 return dp[0][n - 1]
The counterintuitive move (thinking about the last balloon popped instead of the first) is what makes interval DP hard. The tell for this pattern: operations on a sequence where each operation changes what’s adjacent to what.
Practice: Burst Balloons (312), Minimum Cost to Cut a Stick (1547), Strange Printer (664).
Pattern 8: Palindrome DP
The shape: anything involving palindromic substrings or partitions.
The workhorse is a table where is_pal[i][j] records whether s[i..j] is a palindrome, built from shorter spans outward. Palindrome Partitioning II (minimum cuts) combines it with 1D DP:
1def min_cut(s):
2 n = len(s)
3 is_pal = [[False] * n for _ in range(n)]
4 for i in range(n - 1, -1, -1):
5 for j in range(i, n):
6 is_pal[i][j] = (s[i] == s[j]) and (j - i < 2 or is_pal[i+1][j-1])
7
8 cuts = [0] * n
9 for j in range(n):
10 if is_pal[0][j]:
11 cuts[j] = 0
12 continue
13 cuts[j] = min(cuts[i - 1] + 1 for i in range(1, j + 1) if is_pal[i][j])
14 return cuts[-1]
Two patterns stacked: a 2D palindrome table feeding a 1D “minimum cuts ending here” DP. Layered problems like this are exactly what Day 39: Palindrome Partitioning trains.
Practice: Longest Palindromic Substring (5), Palindromic Substrings (647), Palindrome Partitioning II (132).
Pattern 9: Grid Path DP
The shape: move through a 2D grid (usually right/down only), counting paths or optimizing a path cost.
State: dp[r][c] = answer for reaching cell (r, c). Recurrence: combine top and left neighbors.
1def min_path_sum(grid):
2 rows, cols = len(grid), len(grid[0])
3 dp = [float('inf')] * cols
4 dp[0] = 0
5 for r in range(rows):
6 dp[0] += grid[r][0]
7 for c in range(1, cols):
8 dp[c] = grid[r][c] + min(dp[c], dp[c - 1])
9 return dp[-1]
Grid DP is the gentlest 2D pattern and a common warm-up question. The interviewer’s follow-up is almost always obstacles (Unique Paths II) or space reduction to one row, shown above.
Practice: Unique Paths (62), Minimum Path Sum (64), Maximal Square (221).
Pattern 10: State Machine DP
The shape: at each step you’re in one of a few named states, with rules about transitions. The stock-trading series is the flagship.
Best Time to Buy and Sell Stock with Cooldown (LeetCode 309):
1def max_profit(prices):
2 hold, sold, rest = float('-inf'), 0, 0
3 for p in prices:
4 hold, sold, rest = (
5 max(hold, rest - p), # keep holding, or buy today
6 hold + p, # sell today
7 max(rest, sold), # do nothing (cooldown ends)
8 )
9 return max(sold, rest)
Draw the states as circles and transitions as arrows before writing any code. The diagram is the solution, and drawing it on the whiteboard communicates your model to the interviewer for free.
Practice: the entire Best Time to Buy and Sell Stock series (121, 122, 123, 188, 309, 714).
Complexity Cheat Sheet
| # | Pattern | Time | Space (optimized) | Canonical problem |
|---|---|---|---|---|
| 1 | 1D DP | O(n) | O(1) | House Robber |
| 2 | 0/1 Knapsack | O(n·W) | O(W) | Partition Equal Subset Sum |
| 3 | Unbounded Knapsack | O(n·W) | O(W) | Coin Change |
| 4 | LCS | O(m·n) | O(min(m, n)) | Longest Common Subsequence |
| 5 | LIS | O(n²) → O(n log n) | O(n) | Longest Increasing Subsequence |
| 6 | Edit Distance | O(m·n) | O(min(m, n)) | Edit Distance |
| 7 | Interval DP | O(n³) | O(n²) | Burst Balloons |
| 8 | Palindrome DP | O(n²) | O(n²) | Palindrome Partitioning II |
| 9 | Grid Paths | O(m·n) | O(n) | Minimum Path Sum |
| 10 | State Machine | O(n·k) | O(k) | Stock with Cooldown |
If big-O analysis itself is shaky, Day 3: Introduction to Time Complexity is the prerequisite for everything in this table.
Recommended Study Order
Don’t study these in numerical order. Study them so each pattern adds one idea to the last:
- 1D DP (Pattern 1): learn state and recurrence in one dimension.
- Grid Paths (Pattern 9): same idea, two dimensions, still easy.
- 0/1 Knapsack → Unbounded (Patterns 2, 3): the take-or-leave decision, then the loop-direction twist.
- LCS → Edit Distance (Patterns 4, 6): two-sequence states, then a third branch.
- LIS (Pattern 5): “ending at i” states plus the binary search upgrade.
- Palindrome DP (Pattern 8): 2D tables over one string.
- State Machine (Pattern 10): named states and transitions.
- Interval DP (Pattern 7): last, because the length-loop and “last operation” trick assume everything before it.
This is essentially the sequencing of Days 30–39 in our curriculum, and it’s deliberate: each day adds exactly one new idea. If you’d rather follow that plan than assemble your own, the full 60-day curriculum covers DP in week 5 with all the recursion prerequisites in place. Create a free account to track your progress through it. And since DP recurrences are recursion with a memory, make sure recursion itself is solid first.
Related Articles
- Day 30: Dynamic Programming Introduction
- Day 33: The Knapsack Problem
- Recursion for Interviews: Think Before You Code
- Backtracking Explained: N-Queens to Subsets
- The Best FAANG Interview Prep Resources in 2026 (Free + Paid)
Happy coding, and we’ll see you in the next lesson!