Dynamic Programming Patterns Every FAANG Candidate Must Know (2026)

Why Dynamic Programming Dominates FAANG Algorithmic Rounds

Dynamic programming is the algorithmic technique of solving a problem by combining solutions to overlapping subproblems, and in 2026 it accounts for roughly one in four hard problems asked across FAANG coding rounds. Nearly every DP question reduces to one of seven patterns: linear DP, 2D grid DP, subsequence DP, knapsack, interval DP, tree DP, or bitmask DP. Recognizing the pattern in the first two minutes of the interview is the difference between a clean, confident solve and forty minutes of recursive guesswork.

The reason DP is so common is the same reason it intimidates candidates. A correct DP solution requires three sharp skills tested simultaneously: identifying the correct state, writing a recurrence that composes smaller solutions into larger ones, and choosing a memoization or iteration order that makes the recurrence efficient. Each is a separate failure point. Candidates who memorize problems without internalizing the patterns can solve the problems they have seen but freeze on small variations — and small variations are exactly what FAANG interviewers favor.

This reference covers all seven patterns with the same structure: a signature ("if you see X, think Y"), a Python template, three representative LeetCode problems with difficulty ratings, and the common pitfalls that cost candidates the offer. The closing section consolidates everything into a pattern-recognition cheat sheet and a problem-by-difficulty matrix.

Pattern 1: Linear DP

Linear DP is the pattern where the state depends on a small fixed number of previous indices in a one-dimensional sequence. The recurrence usually has the form dp[i] = f(dp[i-1], dp[i-2], ...). This is the simplest DP family and the one candidates encounter first.

The signature is straightforward: if the problem walks forward through a 1D array or sequence and the answer at position i depends only on a small window of recent positions, the pattern is linear DP. Fibonacci numbers, climbing stairs, house robber, and most stock-trading variants all fit here.

Template:

def linear_dp(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [0] * n
    dp[0] = nums[0]
    if n >= 2:
        dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]

Three representative problems:

• Climbing Stairs (LeetCode #70, Easy) — the canonical entry point. dp[i] = dp[i-1] + dp[i-2].
• House Robber (LeetCode #198, Medium) — choose-or-skip on a linear array. dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
• Best Time to Buy and Sell Stock with Cooldown (LeetCode #309, Medium) — multi-state linear DP with three states per index (held, sold, rest).

Common pitfalls: missing base cases for n == 0 and n == 1; forgetting that the choose-or-skip recurrence is the standard form, not a clever insight; failing to mention the O(1) rolling-variable space optimization when the interviewer asks. The space follow-up is asked almost every time on linear DP problems, and a candidate who has not rehearsed it loses easy points.

Pattern 2: 2D Grid DP

2D grid DP is the pattern where the state is a position (i, j) on a two-dimensional grid and transitions are local moves — typically right, down, or diagonal. The recurrence has the form dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

The signature is the cleanest of any DP family: the problem statement gives you a grid, asks for a path or count over the grid, and the moves are restricted to a small fixed set of directions. Unique paths, minimum path sum, maximal square, and dungeon game all fit here. If the problem allows arbitrary movement in any direction, it is not 2D grid DP — it is BFS or Dijkstra.

Template:

def grid_dp(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[m - 1][n - 1]

Three representative problems:

• Unique Paths (LeetCode #62, Medium) — count paths from top-left to bottom-right with right/down moves only. dp[i][j] = dp[i-1][j] + dp[i][j-1].
• Minimum Path Sum (LeetCode #64, Medium) — minimize the sum along the path. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
• Maximal Square (LeetCode #221, Medium) — find the largest square of 1s. dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the cell is 1.

Common pitfalls: forgetting to initialize the first row and first column; reusing the input grid as the dp table without realizing it mutates the input (occasionally fine, but flag it); not noticing that dp[i][j] only needs the previous row, which compresses space from O(mn) to O(n).

Pattern 3: Subsequence DP

Subsequence DP is the pattern where the state is a pair of indices (i, j) into one or two sequences, and the recurrence asks whether the characters at those indices match or differ. This is the most heavily tested DP family at FAANG in 2026 because it covers longest common subsequence, longest increasing subsequence, edit distance, and their many variants.

The signature: the problem mentions subsequences, common substrings, edit operations, or transformations between two strings or arrays. Two-pointer indices walking through the input(s) are almost always the right state.

Template for two-sequence subsequence DP:

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[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]

Template for single-sequence LIS (the patience-sorting O(n log n) version is preferred at senior levels):

from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Three representative problems:

• Longest Common Subsequence (LeetCode #1143, Medium) — the canonical two-sequence DP.
• Longest Increasing Subsequence (LeetCode #300, Medium) — the canonical one-sequence DP. The O(n^2) DP is acceptable; the O(n log n) patience-sort form is a senior-level signal.
• Edit Distance (LeetCode #72, Hard) — three operations (insert, delete, replace) at each position. dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) on mismatch.

Common pitfalls: confusing subsequence (preserves order, allows gaps) with substring (contiguous); writing the base case dp[0][j] = 0 for LCS but dp[0][j] = j for edit distance and getting them backward; missing that LIS has a faster O(n log n) solution when the interviewer pushes on complexity.

Mini Q&A: Is "longest palindromic subsequence" subsequence DP or interval DP? It is most naturally written as interval DP (state is a range [i, j]), although it can also be expressed as LCS between the string and its reverse. Both solutions are accepted, but the interval form is what most interviewers expect.

Pattern 4: Knapsack DP

Knapsack DP is the pattern where a set of items, each with a weight and a value, must be selected subject to a capacity constraint. The 0/1 variant allows each item at most once; the unbounded variant allows unlimited copies. Coin change, partition equal subset sum, and target sum all reduce to knapsack.

The signature: the problem gives a list of items (numbers, coins, tasks) and asks for a count, a minimum, or a yes/no over selections that respect a capacity, target, or sum. Whenever the problem says "subset of these numbers that sums to X" or "fewest coins to make change for X," it is knapsack.

0/1 knapsack template (with space-optimized 1D array):

def zero_one_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for c in range(capacity, weights[i] - 1, -1):
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
    return dp[capacity]

Unbounded knapsack template (note the forward iteration on capacity):

def unbounded_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for c in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= c:
                dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
    return dp[capacity]

Three representative problems:

• Coin Change (LeetCode #322, Medium) — unbounded knapsack with dp[amount] = min(dp[amount - coin] + 1).
• Partition Equal Subset Sum (LeetCode #416, Medium) — 0/1 knapsack reframed as "can we hit target = total/2."
• Target Sum (LeetCode #494, Medium) — 0/1 knapsack after algebraic rewriting to convert sign choices into a subset-sum problem.

Common pitfalls: iterating capacity forward instead of backward for 0/1 knapsack, which lets each item be used multiple times by mistake; forgetting the dp[0] = 0 base case for the count variants and dp[0] = 1 for the "number of ways" variants; using float('inf') for unreachable states in coin-change minimization and then forgetting to convert back to -1 for the final answer.

Pattern 5: Interval DP

Interval DP is the pattern where the state is a contiguous range [i, j] of the input, and the recurrence considers every possible split point k within the range. The recurrence has the form dp[i][j] = min/max over k of (dp[i][k] + dp[k+1][j] + cost(i, k, j)).

The signature: the problem operates on a sequence and the optimal answer for a range depends on choosing one "last operation" inside the range — a last balloon to burst, a last stone to remove, a last pair of parentheses to evaluate. Whenever the problem rewards picking the right order of operations, interval DP is usually the right tool.

Template:

def interval_dp(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('-inf')
            for k in range(i, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(nums, i, k, j))
    return dp[0][n - 1]

Three representative problems:

• Burst Balloons (LeetCode #312, Hard) — the canonical interval DP. The trick is that the state is "balloons in this range not yet burst" and the split k is the last balloon to burst.
• Stone Game (LeetCode #877, Medium) — game theory phrased as interval DP. dp[i][j] is the maximum score the current player can achieve over [i, j].
• Minimum Cost to Merge Stones (LeetCode #1000, Hard) — interval DP with an extra dimension for the number of piles remaining in the range.

Common pitfalls: iterating i and j directly instead of iterating by length (which produces a wrong dependency order); choosing the wrong meaning for the split k (last operation vs first operation — for burst balloons it must be the last); failing to add boundary sentinels (the 1 on each end of Burst Balloons makes the recurrence clean and is easy to forget).

Pattern 6: Tree DP

Tree DP is the pattern where the state is associated with a node in a tree, and the answer at each node is computed from the answers at its children. The recurrence is naturally written as a post-order traversal that returns one or more values per node.

The signature: the problem operates on a tree (binary or general) and asks for a global optimum that can be decomposed into "best answer over this subtree." Robber on a tree, tree diameter, and longest univalue path all fit here.

Template — return a tuple of states per node:

def tree_dp(root):
    def dfs(node):
        if not node:
            return (0, 0)
        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)
        rob = node.val + left_skip + right_skip
        skip = max(left_rob, left_skip) + max(right_rob, right_skip)
        return (rob, skip)
    return max(dfs(root))

Three representative problems:

• House Robber III (LeetCode #337, Medium) — the canonical tree DP. Each node returns two states: best answer if this node is robbed, best if it is skipped.
• Diameter of Binary Tree (LeetCode #543, Easy) — each node returns its height, and the global answer is updated with left_height + right_height at every node.
• Binary Tree Maximum Path Sum (LeetCode #124, Hard) — each node returns the best downward path through it; the global answer considers paths that bend at the node.

Common pitfalls: returning the wrong thing from the recursion — the function must return what is useful for the parent (e.g., a single best downward path), while the global answer is updated as a side effect; forgetting the null-node base case; mixing up "best path through this node" (used globally) with "best path starting from this node going down" (returned to the parent).

Mini Q&A: Why does Binary Tree Maximum Path Sum need two separate values? Because the path through a node can use both children (making a bent path that is the global answer at this node) or only one child (extending into the parent's path). The recursion returns the second; the global answer captures the first.

Pattern 7: Bitmask DP

Bitmask DP is the pattern where the state encodes a subset of a small set of elements (typically up to 20-22 elements) as the bits of an integer. The recurrence transitions between subsets by adding or removing one element. Bitmask DP is the heaviest of the seven patterns and appears mostly at companies with strong algorithmic loops.

The signature: the problem operates on a small set of elements (often a hint is n <= 16 or n <= 20) and the answer depends on which subset of elements has been processed. Travelling salesman variants, assignment problems, and partition problems with small input sizes all qualify.

Template — TSP-style bitmask DP:

def tsp(dist):
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask >> u) & 1:
                continue
            if dp[mask][u] == INF:
                continue
            for v in range(n):
                if (mask >> v) & 1:
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
    return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(1, n))

Three representative problems:

• Travelling Salesman (Held-Karp formulation, classic) — the canonical bitmask DP. State is (visited_mask, current_city).
• Partition to K Equal Sum Subsets (LeetCode #698, Medium) — bitmask over which numbers have been placed.
• Shortest Path Visiting All Nodes (LeetCode #847, Hard) — BFS with state (node, visited_mask), conceptually a bitmask DP.

Common pitfalls: forgetting to check that bit u is in mask before transitioning out of it; using 1 << n states in Python without realizing the state space explodes at n > 22; confusing the role of the leading dimension (mask) with the trailing dimension (current node).

Pattern Recognition Cheat Sheet

The fastest way to internalize the seven patterns is to map signatures to templates in a single table. The version below is the cheat sheet experienced candidates carry into the interview as a mental model.

DP Problems by Difficulty Matrix

A complementary view is by difficulty. The matrix below organizes the most asked DP problems across FAANG in 2026 by pattern and LeetCode difficulty. Candidates working through this matrix in order — easy across all seven patterns, then medium, then hard — develop pattern recognition far faster than working linearly through any single pattern's hardest problems.

Top-Down vs Bottom-Up: When to Pick Which

Both top-down memoization and bottom-up tabulation produce the same answer, but they differ in three practical ways that matter in the interview.

Top-down memoization mirrors the recursive definition directly, which means it is easier to derive on the spot and harder to get wrong. The downside is that Python's recursion limit caps the depth at ~1000 by default, so long inputs can crash. Bottom-up tabulation avoids the recursion entirely and makes space optimization (rolling arrays, O(1) state) much more natural. The downside is that it requires a correct iteration order, which is easy to get wrong for interval DP, 2D grid DP with diagonals, or any DP with non-trivial dependency structure.

The recommendation: write top-down memoization first in the interview. Talk through the recurrence as you write it. Once the interviewer agrees the recurrence is correct, mention that the bottom-up version reduces space to O(n) or O(1) and offer to convert. This sequencing covers both forms without requiring the candidate to commit to the harder one first. The same staging strategy applies to other algorithm-heavy loops — see the hardest LeetCode questions asked in real FAANG interviews for the broader framing.

Common DP Mistakes in Interviews

Across thousands of FAANG DP interviews, the same failure patterns repeat. Avoiding them is the highest-leverage thing a candidate can do in the last week before the interview.

• Defining the state ambiguously. "Let dp[i] be the best answer up to index i" is not a definition unless "best answer" is precise. State definitions must specify whether index i is included or excluded and what "best" means.
• Skipping the recurrence derivation. Candidates who write the recurrence directly without verbalizing the case split (include vs exclude, match vs mismatch, split at k) leave the interviewer unable to follow. Narrate the case split aloud.
• Confusing subsequence and substring. Subsequence preserves order but allows gaps; substring is contiguous. The wrong recurrence for the wrong variant produces wrong answers that look almost right.
• Forgetting base cases. The recurrence is usually correct; the base cases are usually where the bug is. Walk through dp[0] and the first row/column explicitly before running the recurrence.
• Optimizing prematurely. Jumping to O(1) space rolling variables before establishing the full 2D DP makes the code unreadable and the debugging impossible. Always write the full version first.
• Misordering iteration in bottom-up. 2D grid DP needs increasing i and j; interval DP needs increasing length; bitmask DP needs increasing popcount or natural integer order. The wrong order produces silently wrong answers.
• Confusing "count" vs "exists" vs "minimum." Count problems initialize dp[0] = 1; existence problems initialize dp[0] = True; minimum problems initialize dp[0] = 0 and the rest to infinity. Mixing these up is a top-five cause of wrong-answer bugs.

These same communication and process failures show up across coding rounds more broadly — the deeper analysis in why qualified candidates fail technical interviews covers the dynamics in detail.

Where DP Lives in the 2026 FAANG Loop

Different companies weight DP differently. Knowing where it appears helps candidates allocate preparation time. Google asks DP in roughly 30% of its medium-hard coding rounds in 2026, often as the second round after a warm-up. Meta uses DP in around 20% of medium-hard rounds and favors the subsequence and 2D grid families. Amazon asks DP less often than its peers — closer to 15% — and favors knapsack and linear DP variants. Apple and Netflix are closer to Google's mix.

Outside FAANG, the picture shifts. Jane Street and similar quantitative shops ask DP frequently and often in non-standard formulations that require deriving the state from scratch. Palantir asks DP in the algorithmic round but weights system thinking more heavily. Product companies like Notion and Linear ask DP less often, preferring practical problems with collaborative debugging. The implication: candidates targeting Google or Jane Street should spend disproportionate time on interval and bitmask DP; candidates targeting Amazon should focus on linear DP and knapsack.

The DP mix shows up in coding assessments too. Filtered assessments such as those covered in does CodeSignal detect AI in 2026 and coderpad cheating detection in 2026 lean medium DP, while on-site loops favor harder DP variants where pattern recognition is the differentiator.

How to Practice DP in the Final Two Weeks

The most effective last-two-weeks preparation is structured by pattern rather than by problem count. The pattern below produces durable recognition rather than fragile memorization.

Days 1-3: Linear DP. Solve four problems with full state definitions written out before coding. Then re-solve them 48 hours later from scratch. Days 4-6: 2D grid DP. Same drill. Days 7-9: Subsequence DP. This pattern gets the most volume — six problems instead of four, because it is the most asked. Days 10-11: Knapsack. Days 12-13: Interval DP. Day 14: Tree DP and bitmask DP combined.

Throughout, narrate the state and recurrence out loud before writing code. The interview format rewards verbalized DP derivation, and silent practice does not build that skill. Recording a mock and watching it back is the fastest way to identify whether the verbal derivation is clear.

Final Word

The seven patterns above cover almost every DP problem that has been asked at FAANG in 2026, but pattern coverage alone is not enough. The candidates who consistently pass DP rounds combine three things: instant pattern recognition from the signature, clean state definitions that a colleague could read, and disciplined narration that brings the interviewer along through the derivation. The candidates who fail almost always have one of the three — and not the other two. Practice all three together, in interview-like conditions, and the DP round becomes a strength rather than a hazard.