Of all the topics in FAANG interview preparation, dynamic programming causes the most anxiety, and for the most fixable reason.
Most candidates try to learn DP by memorising solutions. They watch a video, follow the logic, feel like they understand it, and then blank when they see a DP problem they haven't seen before.
That's not a knowledge gap. It's a method gap.
This guide teaches dynamic programming the way that actually works for interviews: by learning the patterns that underlie entire families of DP problems, so you can recognise and solve questions you've never encountered before.
TL;DR - What You Actually Need to Know
- DP is about breaking a problem into overlapping subproblems and storing results to avoid recomputation
- There are two implementation approaches: memoization (top-down) and tabulation (bottom-up)
- Most FAANG DP questions fall into 6–7 core patterns, learn the patterns, not individual solutions
- The goal isn't to memorise, it's to recognise problem structure fast enough to apply the right pattern under a timer
What Is Dynamic Programming?
Dynamic programming is an algorithmic technique for solving problems that have two properties:
1. Overlapping subproblems: the problem can be broken into smaller subproblems that repeat. Computing the same subproblem multiple times (as in naive recursion) is wasteful.
2. Optimal substructure: the optimal solution to the overall problem can be constructed from the optimal solutions of its subproblems.
When both properties hold, DP stores the result of each subproblem the first time it's computed, either in a memo table (top-down) or built up iteratively (bottom-up), so it's never computed twice.
Simple example: Fibonacci numbers. The naive recursive approach recomputes fib(3) dozens of times when calculating fib(10). DP stores each result once, making the solution O(n) instead of O(2ⁿ).
Memoization vs. Tabulation: Which to Use?
Which to use in interviews: Start with memoization if the recursive structure is clear to you, it's usually faster to write and easier to explain. Switch to tabulation if the interviewer asks for an iterative solution or if the recursion depth would cause a stack overflow.
The best candidates can move between both. Practice both approaches for every DP problem you solve.
The 7 Core DP Patterns for FAANG Interviews
Pattern 1: Linear DP (1D)
What it is: The solution at position i depends only on a constant number of previous positions.
Recognise it when: The problem involves a single array or sequence, and the answer at each position builds from earlier answers.
Classic problems:
- Climbing Stairs
- House Robber
- Maximum Subarray (Kadane's Algorithm)
- Coin Change
- Word Break
Template thinking: Define dp[i] as the answer for the first i elements. Find the recurrence: how does dp[i] depend on dp[i-1], dp[i-2], etc.? Set base cases. Fill the table.
Pattern 2: Grid DP (2D)
What it is: The solution at position (i, j) depends on adjacent positions in a 2D grid.
Recognise it when: The problem involves a matrix, grid, or two sequences, and movement/choices are constrained.
Classic problems:
- Unique Paths
- Minimum Path Sum
- Longest Common Subsequence
- Edit Distance
- Interleaving String
Template thinking: Define dp[i][j] as the answer for the subproblem ending at row i, column j. Movement is usually from top, left, or diagonal. Fill the grid row by row.
Pattern 3: Knapsack DP
What it is: Given a set of items with weights and values, determine the maximum value you can achieve within a weight constraint.
Recognise it when: The problem involves choosing a subset of items to maximise or satisfy a target, with a capacity or budget constraint.
Classic problems:
- 0/1 Knapsack
- Partition Equal Subset Sum
- Target Sum
- Last Stone Weight II
Template thinking: dp[i][w] = maximum value using first i items with weight capacity w. For each item, decide: include it (subtract its weight, add its value) or exclude it (carry forward the previous best).
Pattern 4: Unbounded Knapsack
What it is: Same as knapsack, but each item can be used an unlimited number of times.
Recognise it when: The problem asks for a combination that reaches a target, and repetition is allowed.
Classic problems:
- Coin Change (minimum coins)
- Coin Change 2 (number of combinations)
- Rod Cutting
- Integer Break
Template thinking: Because items can be reused, when you include an item, you don't move to the next item — you stay at the same item and reduce the remaining capacity.
Pattern 5: Longest Increasing Subsequence (LIS)
What it is: Find the longest subsequence in an array where elements are strictly increasing.
Recognise it when: The problem asks for the longest/shortest subsequence with a monotonic constraint, or involves scheduling problems with dependency chains.
Classic problems:
- Longest Increasing Subsequence
- Number of Longest Increasing Subsequences
- Russian Doll Envelopes
- Minimum Number of Arrows to Burst Balloons
Template thinking: dp[i] = length of longest increasing subsequence ending at index i. For each i, check all j < i where nums[j] < nums[i] and update dp[i] = max(dp[i], dp[j] + 1). O(n²) solution; O(n log n) with binary search.
Pattern 6: DP on Intervals
What it is: The problem asks about an optimal value over a contiguous subarray or interval, and the answer for a larger interval depends on smaller intervals.
Recognise it when: The problem involves partitioning or merging ranges, and you need to consider all possible split points.
Classic problems:
- Burst Balloons
- Matrix Chain Multiplication
- Palindrome Partitioning II
- Strange Printer
Template thinking: dp[i][j] = answer for the subarray from index i to j. For each length of subarray, try every split point k and combine dp[i][k] and dp[k+1][j].
Pattern 7: DP on Strings
What it is: Problems where the state involves positions in one or two strings, and the solution builds from shorter substrings.
Recognise it when: The problem asks about matching, editing, or comparing substrings — often involving two strings at once.
Classic problems:
- Longest Common Subsequence
- Edit Distance
- Distinct Subsequences
- Longest Palindromic Subsequence
- Regular Expression Matching
Template thinking: Define dp[i][j] in terms of the first i characters of string 1 and first j characters of string 2. The recurrence depends on whether s1[i] == s2[j] and what operation you're performing.
How to Approach a DP Problem in an Interview (Step by Step)
When you see a new DP problem in an interview, run through this sequence:
Step 1: Identify the properties. Does this problem have overlapping subproblems? Can I build the optimal answer from optimal subproblems? If yes to both, DP is likely the right approach.
Step 2: Recognise the pattern. Which of the 7 patterns does this problem resemble? Look at the input structure (array, grid, two strings), the constraint type (capacity, target sum, length), and the question being asked (max, min, count, true/false).
Step 3: Define the state. What does dp[i] (or dp[i][j]) represent? Be precise. "The maximum profit achievable using the first i items" is a clean state. "The answer up to i" is too vague.
Step 4: Write the recurrence. How does dp[i] depend on earlier states? Derive this from first principles, don't try to recall a formula.
Step 5: Set base cases What are the smallest subproblems you can answer directly? These are your base cases.
Step 6: Choose top-down or bottom-up Start with whichever is clearer. Implement, test on a small example.
Step 7: Optimise space if asked Many 2D DP solutions can be reduced to 1D if only the previous row is needed. Raise this proactively, it signals depth.
The Most Common DP Mistakes in Interviews
Trying to jump straight to the recurrence. The recurrence only makes sense after you've defined the state precisely. Candidates who skip state definition usually end up with a recurrence that doesn't hold.
Confusing the state with the index. dp[i] is not "the answer at position i" - it's the answer to a specific subproblem that ends at or involves position i. The difference matters when setting up your recurrence.
Skipping base cases. Base cases aren't obvious formalities, they're the foundation your recurrence builds on. Missing one breaks the entire table.
Not talking through the approach before coding. In a FAANG interview, writing a DP solution without explaining your state definition first tells the interviewer nothing about your reasoning. Always define the state and recurrence out loud before writing code.
Memorising solutions instead of patterns. If you can only solve LeetCode 322 (Coin Change) because you've seen it before, you can't solve a variation you haven't. Learning the unbounded knapsack pattern means you can solve any coin-change variant on sight.
Practising DP the Right Way
Week 1: Linear DP + unbounded knapsack, these share structure and build intuition fast
Week 2: Grid DP + 0/1 knapsack, the most common FAANG DP categories
Week 3: LIS pattern + DP on strings, harder patterns with more interview appearances
Week 4: Interval DP, save this last; it's the least common and most complex
For each problem: attempt without looking at the solution first. Define state on paper. Derive recurrence. Implement. Then check the solution and compare approaches.
How Mock Interviews Expose DP Gaps
Solving DP problems alone in your IDE is the most misleading form of preparation for this topic.
In a real interview, you have to:
- Identify that a problem requires DP in under 2 minutes
- Define your state out loud before writing a single line
- Handle a follow-up asking you to reduce space complexity
- Debug when your recurrence is wrong, while the interviewer is watching
All of these are skills you only build by practicing under conditions that mirror the real thing.
At Intervue.io, mock coding sessions include DP problems calibrated to the level of difficulty your target company uses, and you receive specific feedback on how clearly you explained your approach, not just whether your code was correct.
👉 Practice DP problems in a mock interview on Intervue.io
FAQs
How do I know if a problem needs DP? Look for two signals: the problem asks for a maximum, minimum, count, or true/false across all possibilities; and naive recursion would revisit the same subproblems. If both apply, DP is almost certainly the right approach.
Should I learn memoization or tabulation first? Learn memoization first, it mirrors the recursive structure of the problem and is usually faster to implement. Once you understand the state and recurrence, converting to tabulation is straightforward.
What's the hardest DP pattern for FAANG interviews? Interval DP (like Burst Balloons) and DP on strings with two sequences (like Edit Distance) tend to be the hardest. LIS and its variants are also frequently misjudged by candidates who don't recognise the pattern fast enough.
How many DP problems should I solve before interviews? Aim for 25–35 problems across all 7 patterns, with genuine understanding of the state and recurrence for each. Shallow coverage of 80 DP problems is weaker preparation than deep coverage of 30.
Can I use Python for DP in FAANG interviews? Yes, Python is widely accepted at all FAANG companies for coding interviews. The recursion limit in Python can be an issue for deep memoization; use sys.setrecursionlimit() or prefer tabulation for very deep recursion trees.
