Dynamic Programming is the filter question that separates experienced engineers from novices in coding interviews. Not because DP is inherently difficult—it's not—but because it requires a specific way of thinking that many engineers never develop. If you can recognize that a problem is a DP problem and immediately sketch the state transitions, interviewers are impressed. If you freeze when you see a DP problem, you've lost the interview. This guide walks you through the 20 most common DP patterns you'll encounter in FAANG interviews, with frameworks for solving each one.

Why Interviewers Love DP Questions

Before diving into patterns, let's understand why interviewers ask DP questions in the first place.

DP questions test multiple skills simultaneously: Can you break down a complex problem into subproblems? Can you recognize overlapping substructure? Can you optimize a naive solution through memoization or tabulation? Can you implement it cleanly without bugs? This is why a single DP question can take up an entire 45-minute interview round.

The beauty of DP for interviewers is that the bar is flexible. A weak solution is brute force with memoization (which you can salvage). A good solution is optimized memoization. A great solution is optimized bottom-up tabulation with space optimization. This allows interviewers to differentiate between candidates clearly.

Pattern 1: Linear DP (House Robber, Paint House)

Linear DP is the simplest DP pattern. You have a sequence of elements, and you need to make decisions about each element, where the decision depends on previous decisions.

The Framework:

• State: dp[i] = answer for elements 0 to i
• Transition: dp[i] = f(dp[i-1], dp[i-2], ...)
• Base case: dp[0], dp[1]

Classic Problem: House Robber You have houses in a row. If you rob house i, you can't rob house i-1. Maximize total money robbed.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

If you rob house i, you get nums[i] plus the best result from houses up to i-2. If you don't rob house i, you get the best result from houses up to i-1. You choose the max.

When You See It: Any problem where you're optimizing some metric on a sequence and past decisions constrain future decisions.

Pattern 2: 2D DP on Grids

Many interview problems involve navigating or computing values on a 2D grid. These are straightforward extensions of linear DP.

The Framework:

• State: dp[i][j] = answer for the subgrid from (0,0) to (i,j)
• Transition: dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j])
• Base case: dp[0][j], dp[i][0]

Classic Problem: Unique Paths Count the number of ways to reach bottom-right corner of an m x n grid, moving only right or down.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

You can reach (i,j) by coming from above or from the left. Total ways = ways to reach above + ways to reach left.

When You See It: Grid-based problems, especially path counting, minimum cost paths, or dynamic range calculations.

Pattern 3: String Matching DP (Edit Distance, Longest Common Subsequence)

String problems are a huge category in DP. The key insight is that you're comparing characters at different positions.

The Framework:

• State: dp[i][j] = answer when considering first i characters of string 1 and first j characters of string 2
• Transition: If s1[i-1] == s2[j-1], then dp[i][j] = dp[i-1][j-1] + something. Otherwise, try different operations.
• Base case: dp[0][j] = j (insert j characters), dp[i][0] = i (delete i characters)

Classic Problem: Edit Distance (Levenshtein Distance) Minimum number of edits (insert, delete, replace) to transform string s1 into string s2.

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],      # delete from s1
        dp[i][j-1],      # insert into s1
        dp[i-1][j-1]     # replace
    )

When You See It: Any string comparison, auto-complete, spell checking, or transformation problem. This is incredibly common.

Pattern 4: Unbounded Knapsack

Unlike 0/1 knapsack where you can use each item once, unbounded knapsack lets you use items unlimited times.

The Framework:

• State: dp[w] = maximum value using weight capacity w
• Transition: For each item, dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
• Base case: dp[0] = 0

Classic Problem: Coin Change (Minimum Coins) Given coins of different denominations, find the minimum number of coins to make amount X.

dp[amount] = min(dp[amount], 1 + dp[amount - coin])

For each coin, if using that coin is viable, the answer is either the current answer or 1 (the coin) plus the answer for the remaining amount.

When You See It: Coin problems, unlimited supplies, optimization with repetition allowed.

Pattern 5: Tree DP

Tree DP involves computing values for each node, where the value depends on its subtrees.

The Framework:

• DFS from leaves to root
• For each node, compute answer based on children's answers
• Return the answer for the root

Classic Problem: Maximum Path Sum in Binary Tree Find the maximum sum of any path in the tree (path doesn't need to include root).

def dfs(node):
    if not node:
        return 0
 
    left_max = dfs(node.left)
    right_max = dfs(node.right)
 
    # Path through this node
    max_path = node.val + left_max + right_max
    # Update global max
    self.max_sum = max(self.max_sum, max_path)
 
    # Return max path starting from this node
    return node.val + max(left_max, right_max)

When You See It: Problems involving binary trees, graphs with parent-child relationships, or dependency graphs.

Pattern 6: Digit DP

Digit DP is less common but appears in Google/Meta interviews. It involves breaking numbers into digits and computing based on constraints.

The Framework:

• Represent numbers as digit sequences
• Track: current position in the number, whether we're still bounded by the limit, other constraints
• Memoize on these states

Classic Problem: Count Numbers in Range Count numbers in range [a, b] with specific digit properties (e.g., no digit appears twice).

This requires thinking about the problem digit-by-digit and handling the "tight" constraint (whether we're still bounded by the original number).

When You See It: Rare, but watch for: "count numbers in range" or "numbers with property X". Digit DP is the approach.

Pattern 7: Interval DP

Interval DP solves problems on subarrays or substrings by building up from smaller intervals to larger ones.

The Framework:

• State: dp[i][j] = answer for subarray/substring from i to j
• Transition: Try splitting at different points k, combine results
• Order matters: iterate by interval length, not by starting position

Classic Problem: Burst Balloons You have balloons. Bursting balloon i gives coins. Problem: coins depend on neighboring balloons. Maximize coins.

dp[i][j] = max over k in [i+1, j-1] of:
    dp[i][k] + burst(k) + dp[k][j]

The insight: think of bursting k last in the range [i, j]. Then when you burst k, neighbors i and j are still alive.

When You See It: Subarray/substring optimization, matrix chain multiplication, optimal binary search tree.

Pattern 8: Partition DP

Partition DP involves partitioning an array or string optimally.

The Framework:

• State: dp[i] = optimal partition of array/string [0, i)
• Transition: dp[i] = min/max over j of: (cost of partition [j, i)) + dp[j]

Classic Problem: Word Break II Break a string into words from a dictionary. Count ways or list all ways.

dp[i] = sum of dp[j] for all j < i where s[j:i] is a valid word

When You See It: Word problems, partitioning problems, matching with dictionaries.

Pattern 9: Game Theory DP

Game theory DP involves two players making optimal moves alternately.

The Framework:

• State: dp[i][j] = optimal score difference when player 1 moves
• Transition: Player 1 chooses max, player 2 chooses min
• Base case: When no moves remain, difference = 0

Classic Problem: Predict the Winner (Game with Piles) Two players alternate taking from piles. Each gets the value of what they take. Who wins with optimal play?

def dp(piles, memo):
    if not piles:
        return 0
    key = tuple(piles)
    if key in memo:
        return memo[key]
 
    # Current player tries each move
    max_gain = 0
    for i in range(len(piles)):
        new_piles = piles[:i] + piles[i+1:]
        # Current player gains piles[i], opponent plays optimally
        gain = piles[i] - dp(new_piles, memo)
        max_gain = max(max_gain, gain)
 
    memo[key] = max_gain
    return max_gain

When You See It: Game problems, minimax scenarios, turn-based competitions.

Pattern 10: Stock Trading DP

Stock trading problems have their own flavor. You have days, prices, and constraints (max transactions, cooldown, etc.).

The Framework:

• State: dp[i][j] = max profit on day i with j transactions completed (or in state j)
• Transition: On day i, either hold stock (carry state forward) or sell (complete transaction)
• Base case: Day 0, 0 transactions

Classic Problem: Best Time to Buy and Sell Stock IV (k transactions) Max profit with at most k transactions (buy-sell pairs).

dp[i][j] = max profit on day i with at most j transactions
dp[i][j] = max(dp[i-1][j], max over t < i of (dp[t-1][j-1] + prices[i] - prices[t]))

When You See It: Stock trading problems, transaction-based optimization.

Pattern 11: LCS (Longest Common Subsequence) Variations

LCS extends to many variations: longest increasing subsequence, longest repeating substring, etc.

The Framework:

• Similar to string matching, but track the longest vs. the count
• Often need to reconstruct the actual subsequence, not just the length

When You See It: Subsequence problems, longest increasing/decreasing subsequence, DNA matching.

Pattern 12: Bitmask DP

Bitmask DP uses a bitmask to represent a set of elements, tracking which have been used.

The Framework:

• State: dp[mask][i] = optimal value using elements in mask, currently at position i
• Transition: Try using each unused element next
• Use case: Small n (usually <= 20)

Classic Problem: Traveling Salesman Problem (Small n) Visit all cities exactly once, minimize distance.

dp[mask][i] = minimum distance to visit cities in mask, ending at city i

When You See It: Small permutation problems, visiting all elements once, optimal assignments.

Pattern 13: Probability DP

DP can solve probability problems where you compute expected values.

The Framework:

• State: dp[state] = expected value or probability from state
• Transition: Weighted sum of next states
• Base case: Terminal states

When You See It: Dice problems, probability calculations, expected value problems.

Pattern 14: State Compression DP

When your state space is large but has structure, you can compress it.

The Framework:

• Identify the essential information needed for memoization
• Compress into a tuple or hash
• Memoize on this compressed state

When You See It: Complex state spaces where not all information matters.

Pattern 15-20: Other Common Patterns

Pattern 15: Subset DP - Generate or count subsets with properties Pattern 16: Permutation DP - Compute on permutations Pattern 17: Graph DP - Shortest paths, longest paths in DAGs Pattern 18: Matching DP - Optimal matching between elements Pattern 19: Counting DP - Count structures (combinations, arrangements) Pattern 20: Optimization DP - General optimization on sequences or structures

How to Approach an Unknown DP Problem

When you encounter a DP problem you don't recognize immediately:

1. Can it be solved recursively? If yes, what are the parameters?
2. Does it have overlapping subproblems? Compute the same thing multiple times?
3. Is there optimal substructure? Does the optimal solution build on optimal sub-solutions?
4. Define your state carefully. What information is essential? What's redundant?
5. Write the recurrence. How does dp[state] relate to smaller states?
6. Memoize aggressively. Start with memoization, then optimize to bottom-up if needed.
7. Verify with examples. Test your DP logic on small inputs.

Common DP Mistakes

Mistake 1: Wrong state definition. If your state doesn't capture enough information, your recurrence breaks.

Mistake 2: Off-by-one errors. Be careful with array indices and inclusive/exclusive boundaries.

Mistake 3: Not handling base cases. Every DP needs proper base cases.

Mistake 4: Memoization without careful hashing. If your state is complex, make sure your hash is correct.

Mistake 5: Not optimizing space. Many DPs can use O(n) space instead of O(n²), but only if you think about it.

Practicing DP Effectively

Here's how to build DP mastery:

1. Do 50 DP problems minimum. LeetCode categorizes them. Do all "easy" DP, then all "medium" DP.
2. For each problem, write the recurrence clearly before coding. This forces you to think before typing.
3. Implement both top-down (memoization) and bottom-up (tabulation) versions. Understand the differences.
4. Optimize space. After solving, ask: can I use less space?
5. Teach it. Explain your solution to someone else. If you can't, you don't understand it.
6. Time yourself. In interviews, you have 45 minutes. Can you code a DP solution in 30 minutes?

Real Interview Scenario

In a real FAANG interview, here's how a DP round typically goes:

• Minute 0-5: You get the problem. It's unfamiliar. You pause, think about whether it's a DP problem.
• Minute 5-10: You define your state and recurrence, talking through your thinking.
• Minute 10-25: You code your solution, explaining as you go.
• Minute 25-35: You test on examples and fix bugs.
• Minute 35-45: You optimize—space complexity, time complexity, special cases.

The interviewer watches to see: Can you recognize DP patterns? Can you define states clearly? Can you implement without bugs? Can you optimize?

Preparing for Your DP Interviews

When you're deep in DP prep and solving problems, there's still that nagging anxiety: will I think clearly when it matters? Will I remember the patterns under pressure? Will I code correctly when an interviewer is watching?

Phantom Code is designed exactly for this scenario. It's an invisible AI assistant that listens to your interviewer and provides instant DP solution guidance in real-time, all through a WhatsApp-like chat interface. It supports all major languages (Python, Java, JavaScript, C++, Golang, SQL, Ruby, Kotlin, Swift), handles DP problems alongside other interview types, and is completely undetectable by screen-sharing and proctoring software. With 20+ undetectability features and real-time audio transcription, you can focus on clearly explaining your approach while getting expert-level help with implementation. Plans start at ₹499/month. Visit phantomcode.co to learn more.

Final Thoughts

Mastering DP patterns is one of the fastest ways to improve your interview performance. Most engineers avoid DP because it seems intimidating. But once you understand the 20 patterns above, DP problems become manageable. You'll recognize the pattern, sketch the state and recurrence, implement it, and move on. That clarity is what interviewers are looking for.

Start with linear DP and grid DP—these are the simplest. Build from there. Within a few weeks of focused practice, DP will no longer be a weakness. It'll be a strength.