7 DP Patterns That Crack 90% of FAANG Problems in 2026

Dynamic programming is the most feared interview pattern. Candidates who confidently grind sliding window for two weeks freeze when they see "dp" in a problem tag, because every DP problem looks brand new. The premise here is simple: it isn't.

About 90% of DP problems reduce to seven archetypal patterns. Once you internalize the patterns, recognition speed compounds. You stop seeing "Edit Distance" and "Longest Common Subsequence" as different problems and start seeing both as Pattern 5. You get the seven templates, thirty LeetCode walkthroughs (4-5 per pattern), and the "recognize-then-template" flowchart that turns DP from a fear tag into a calm-confidence tag.

Why DP feels impossible (and why it isn't)

The "every DP problem looks new" illusion comes from two real properties of DP problems. The problem statement varies wildly (coin change, unique paths, edit distance). The recurrence rarely jumps out from the statement.

Reality: 90% of FAANG DP problems collapse into seven patterns. The pattern is set by the problem's state space, not its surface description. Classify by state space and the recurrence often falls out in 60 seconds.

The 4-step DP recognition framework:

1. Optimal substructure? Does the optimal solution to the problem contain optimal solutions to subproblems? If yes, DP is on the table.
2. Overlapping subproblems? Are the same subproblems solved repeatedly in a naive recursion? If yes, memoization helps.
3. What's the state? Identify the parameters that vary across recursive calls. The state is usually 1-3 dimensions.
4. What's the transition? Express the answer for state S in terms of smaller states.

If you can answer these four questions in 2 minutes for any problem, you're 80% of the way to the solution.

Classify by state space, not surface description. The recurrence falls out of the parameters that vary across recursive calls — usually within 60 seconds.

TL;DR — the 7 DP patterns

The seven patterns, scannable.

• Pattern 1: 1D linear DP (Climbing Stairs, House Robber). State = single index.
• Pattern 2: 2D grid DP (Unique Paths, Min Path Sum). State = (row, col).
• Pattern 3: 0/1 Knapsack (Partition Equal Subset Sum, Target Sum). State = (item index, capacity).
• Pattern 4: Unbounded Knapsack (Coin Change, Combination Sum IV). State = (capacity); items reusable.
• Pattern 5: Longest Subsequence DP (LIS, LCS, Edit Distance). State = (i, j) for two-string problems.
• Pattern 6: Interval DP (Burst Balloons, Matrix Chain). State = (left, right) range.
• Pattern 7: State-machine DP (Buy/Sell Stock, Paint House). State = (index, "what state am I in").

Worth knowing for L5+ candidates: Bitmask DP (subset enumeration), Digit DP (counting numbers with property), Tree DP (post-order DP on trees). Dedicated pillars cover these. Prepping for L4 or below? Deprioritize.

Top-down vs bottom-up — when to use each

Both approaches solve the same problems. The choice matters for whiteboard interviews.

Top-down (memoized recursion):

• Easier to write. Mirrors the recurrence directly.
• Slight overhead from recursion stack and dictionary lookups.
• Default choice for whiteboard. Less off-by-one risk.

Bottom-up (tabulation):

• Faster (no recursion overhead).
• Often allows space optimization (rolling row, rolling variables).
• Required when interviewer asks "iterative please" or "O(1) extra space."

Decision rule: write top-down first. Convert to bottom-up if the interviewer asks for iterative or you need space optimization.

Pattern 1 — 1D linear DP

Template: dp[i] = f(dp[i-1], dp[i-2], ..., arr[i]). State = single index. Often O(1) space with rolling variables.

Problems:

• LC 70 Climbing Stairs (Easy). Fibonacci in disguise.
• LC 198 House Robber (Medium). dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
• LC 213 House Robber II (Medium). Circular array; run House Robber twice (skip first or skip last).
• LC 322 Coin Change (Medium). Overlap with Pattern 4.
• LC 53 Maximum Subarray (Medium). Kadane's algorithm.
• LC 152 Maximum Product Subarray (Medium). Track min AND max because negative times negative is positive.

LC 198 House Robber, fully worked:

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr
    return prev1

Common bug: off-by-one on dp[0] / dp[1] base cases. Always handle the n=0 and n=1 cases explicitly.

Pattern 2 — 2D grid DP

Template: dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j]). Often O(min(m,n)) space with rolling row.

Problems:

• LC 62 Unique Paths (Medium).
• LC 63 Unique Paths II (Medium). With obstacles.
• LC 64 Minimum Path Sum (Medium).
• LC 221 Maximal Square (Medium). dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
• LC 931 Minimum Falling Path Sum (Medium).

LC 221 Maximal Square, fully worked:

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    best = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                best = max(best, dp[i][j])
    return best * best

The key insight on LC 221: dp[i][j] represents the side length of the largest square ending at (i,j). The transition takes the min of three neighbors because a square can only extend if all three neighbors form squares.

Pattern 3 — 0/1 Knapsack

Template: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]). Each item used at most once.

Problems:

• LC 416 Partition Equal Subset Sum (Medium). Can we hit target = sum/2.
• LC 494 Target Sum (Medium). Convert to subset-sum.
• LC 474 Ones and Zeroes (Medium). 2D knapsack.

LC 416 Partition Equal Subset Sum, fully worked:

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for w in range(target, num - 1, -1):  # reverse to avoid using current item twice
            dp[w] = dp[w] or dp[w - num]
    return dp[target]

The "subset sum" trick: any "can we partition" or "can we hit a target" question with a fixed set is 0/1 knapsack. Reverse iteration is critical. Forward iteration would let you use each item multiple times (which is unbounded knapsack).

Pattern 4 — Unbounded Knapsack

Template: dp[w] = min(dp[w-coin] + 1) for all coins. Items reusable.

Problems:

• LC 322 Coin Change (Medium). Minimum coins.
• LC 518 Coin Change II (Medium). Number of ways.
• LC 377 Combination Sum IV (Medium). Order matters here. Careful.

LC 322 Coin Change, fully worked:

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for w in range(1, amount + 1):
        for coin in coins:
            if coin <= w:
                dp[w] = min(dp[w], dp[w - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Order matters bug: for "number of ways" iterate coins outer (LC 518). For "minimum count" iterate amounts outer (LC 322). Swap the loops and you get wrong answers. Common interview trap.

LC 518 vs LC 377: both are "number of ways" but LC 377 counts permutations (order matters), LC 518 counts combinations (order doesn't). The loop order distinguishes them.

Pattern 5 — Longest Subsequence DP

Template: dp[i][j] = dp[i-1][j-1] + 1 if match else max(dp[i-1][j], dp[i][j-1]). State = (i, j) for two-string problems. O(min(m,n)) space.

Problems:

• LC 300 Longest Increasing Subsequence (Medium). O(n^2) DP or O(n log n) patience sort.
• LC 1143 Longest Common Subsequence (Medium). The foundation.
• LC 72 Edit Distance (Hard). 3-operation table.
• LC 583 Delete Operation for Two Strings (Medium). LCS variant.
• LC 1092 Shortest Common Supersequence (Hard).

LC 1143 LCS, fully worked:

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

LC 72 Edit Distance, fully worked:

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

The "two strings" tell: two strings plus a constraint is almost always LCS-family. Recognize this in 90 seconds.

LC 300 LIS, O(n log n) patience-sort version (worth knowing for L5+ where the interviewer probes "can you do better than O(n^2)?"):

from bisect import bisect_left

def lengthOfLIS(nums):
    tails = []
    for n in nums:
        idx = bisect_left(tails, n)
        if idx == len(tails):
            tails.append(n)
        else:
            tails[idx] = n
    return len(tails)

Pattern 6 — Interval DP

Template: dp[i][j] = min/max over k of (dp[i][k] + dp[k+1][j] + cost(i,k,j)). State = (left, right) range. O(n^2) space, O(n^3) time.

Problems:

• LC 312 Burst Balloons (Hard). The "think backwards" insight.
• LC 1547 Minimum Cost to Cut a Stick (Hard).
• LC 1000 Minimum Cost to Merge Stones (Hard).

LC 312 Burst Balloons, fully worked:

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
                )
    return dp[0][n - 1]

The counter-intuitive insight on Burst Balloons: think "which balloon to burst LAST in this interval", not first. Try to think first-burst and the recursion explodes because the neighbors change with each burst. Last-burst makes the neighbors fixed (they're the interval endpoints).

One insight (burst last, not first) is the entire LC 312 solution. Everything else is mechanical interval-DP boilerplate.

This single insight is the difference between solving and not solving LC 312. The canonical "interval DP" interview test.

Pattern 7 — State-machine DP

Template: dp[i][state] = max over prev_state of (dp[i-1][prev_state] + transition(prev_state, state)).

Problems:

• LC 121 Buy/Sell Stock I (Easy). 2 states (held / not).
• LC 309 Buy/Sell Stock with Cooldown (Medium). 3 states.
• LC 188 Buy/Sell Stock IV (Hard). k transactions.
• LC 256 Paint House (Medium). 3 color states.
• LC 265 Paint House II (Hard). k color states.

LC 309 Buy/Sell Stock with Cooldown, fully worked:

def maxProfit(prices):
    if not prices:
        return 0
    held = -prices[0]      # holding stock
    sold = 0               # just sold
    rest = 0               # resting (can buy)
    for i in range(1, len(prices)):
        prev_held, prev_sold, prev_rest = held, sold, rest
        held = max(prev_held, prev_rest - prices[i])
        sold = prev_held + prices[i]
        rest = max(prev_rest, prev_sold)
    return max(sold, rest)

Three states (held, sold, rest) and explicit transitions between them. Draw the state diagram on the whiteboard before coding. The interviewer notices.

The recursion-to-DP transformation flowchart

The 5-step process for converting any naive recursion to DP:

1. Write the recursive solution. Don't worry about efficiency.
2. Identify the parameters that vary. These are your state.
3. Memoize on those parameters. Wrap the recursion in @cache or a manual dict.
4. Convert to bottom-up table. Write the recurrence iteratively.
5. Optionally space-optimize. Roll dimensions if dependencies are local.

Worked example: Climbing Stairs.

Step 1 (recursion):

def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

Step 2 (state): one parameter, n.

Step 3 (memoize):

from functools import cache

@cache
def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

Step 4 (bottom-up):

def climbStairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Step 5 (O(1) space):

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Each step is mechanical. Transform 5 problems this way and the muscle memory compounds.

Space optimization tricks

The four most common space optimizations:

• 1D linear: rolling variables (O(1) instead of O(n)).
• 2D grid: rolling row (O(min(m,n)) instead of O(m*n)).
• Knapsack: reverse iteration to avoid using current row's updated values.
• Subsequence: rolling row or alternating two rows.

Cheat: 80% of DP problems can be space-optimized to O(min(dims)) once you see the pattern. Interviewers love hearing "I can space-optimize this from O(n^2) to O(n)" even when they don't ask you to do it.

When DP is the wrong tool

Recognizing when NOT to use DP is half the battle.

• If the problem asks "find ALL solutions" → backtracking, not DP. DP gives counts or extrema, not enumerations.
• If the problem has a greedy choice property → greedy, not DP. (LC 55 Jump Game II. Greedy beats DP in time and clarity.)
• If the problem is on a tree without overlapping subproblems → tree traversal, not DP.
• If the problem asks "is there ANY solution" with feasibility constraints → BFS/DFS with memoization, not classical DP.

2026-specific FAANG DP expectations

The 2026 interviewer expects you to:

• Recognize the pattern (which of the 7) in under 3 minutes from problem statement.
• Code top-down memoized solution in under 12 minutes for medium problems.
• Answer the "can you space-optimize?" follow-up affirmatively for at least 5 of the 7 patterns.
• Articulate time and space complexity for both top-down and bottom-up versions.

DP problems are also high-leverage in AI-allowed rounds because the AI can write the boilerplate but you have to drive the recurrence design. See What Changed in FAANG Interviews After ChatGPT for context on why DP recognition matters more in 2026 than 2022.

Practice plan — 30 problems in 4 weeks

Four-week practice plan, calibrated to a candidate doing 10-12 hours per week.

• Week 1: Patterns 1+2 (linear + grid). 8 problems: LC 70, 198, 213, 53, 152, 62, 64, 221.
• Week 2: Patterns 3+4 (knapsacks). 6 problems: LC 416, 494, 322, 518, 377, 474.
• Week 3: Pattern 5 (subsequence). 6 problems: LC 300, 1143, 72, 583, 392, 1092.
• Week 4: Patterns 6+7 (interval + state-machine). 10 problems: LC 312, 1547, 1000, 121, 309, 188, 122, 714, 256, 265.

By end of week 4, you should identify the pattern for any DP problem in under 3 minutes and solve mediums in under 25 minutes including dry run.

For the parent pillar covering all 23 patterns FAANG draws from, see 23 LeetCode Patterns That Cover 95% of FAANG Questions. For the frequency-ranked problem list (DP appears 12 times in the top 75), see 75 LeetCode Problems FAANG Asks Most.

FAQ

Is DP harder than other patterns? It feels harder. The 7-pattern framework collapses 90% of it. Once you internalize the patterns, DP is no harder than sliding window. Just different.

Should I learn DP top-down or bottom-up first? Top-down. It mirrors recursion which you already know. Convert to bottom-up only when needed.

How many DP problems should I solve? 30 deeply > 100 shallowly. The pattern recognition is what matters; volume without pattern grouping doesn't compound.

Will FAANG ask me bitmask DP? L5+ rarely. L4 onsite never. New grad onsite never. If you're prepping for L6 staff at quant or HFT, learn it. Otherwise skip.

What's the most common FAANG DP problem? LC 322 Coin Change is the most-asked DP problem at Amazon and Google by our 2026 internal Discord-tracked dataset. LC 198 House Robber and LC 70 Climbing Stairs are the most common phone-screen warmups.

How do I avoid the "I can't see the recurrence" freeze? Write the recursion first, even brute force. The recurrence emerges from the recursion. You can't start with the recurrence as a candidate. Start with the recursive solution and let the parameters reveal themselves.

The verdict

Dynamic programming is feared because the surface variation is huge. The underlying pattern space is small. Seven archetypes cover 90% of FAANG DP problems. Master the seven, build the recursion-to-DP transformation reflex, and DP becomes another comfortable category in your interview repertoire.

If you found this useful, FaangCoder helps candidates iterate to optimal solutions in real interviews. Ask it to walk through the LC 312 "burst last, not first" insight and watch the recurrence fall out. $399 lifetime ($199/mo monthly option). See the Solve demo, Debug demo, or join the Discord to talk to other candidates working through the 7 patterns.