TL;DR: Dynamic programming feels impossible because most people learn it as one giant topic and attack every problem from scratch. It is not one topic. It is a small family of patterns, and six of them cover nearly every DP question you will meet in an interview: Fibonacci-style, 0/1 Knapsack, Unbounded Knapsack, Longest Common Subsequence, Palindromic Subsequence, and Longest Increasing Subsequence. Each has a one-sentence tell and a short template. Learn the six tells, learn the six templates, and DP stops being the topic you pray doesn't come up.
Ask engineers which interview topic they fear most and dynamic programming wins by a landslide. I have watched strong candidates, people who cruise through sliding window and tree problems, freeze the moment a problem smells like DP. And I have also watched candidates calmly dismantle a hard DP question in fifteen minutes. The difference is never raw intelligence. The calm ones had stopped treating DP as one monolithic subject and started treating it as a handful of recognizable shapes.
That is the whole idea of learning patterns instead of problems, applied to the scariest corner of the map. This guide gives you the six shapes.
Why DP feels impossible (and why it isn't)
Every DP problem has the same skeleton: you make a choice at each step, the choices create overlapping subproblems, and greedy picking demonstrably fails, so you must remember the answers to subproblems instead of recomputing them. That's it. That is the entire mystery.
The reason DP still terrifies people is that the same skeleton wears wildly different costumes. "How many ways can you decode this string" and "can you split this array into two equal-sum halves" and "find the longest palindromic subsequence" do not look related. So people solve 50 DP problems as 50 separate puzzles, retain none of them, and conclude they are bad at DP.
They are not bad at DP. They are bad at a filing system nobody gave them. Here is the filing system.
The six patterns at a glance
| Pattern | The tell | Classic problem |
|---|---|---|
| 1. Fibonacci-style | Answer at position i comes from a few previous positions | Climbing Stairs, House Robber |
| 2. 0/1 Knapsack | Pick items once each to hit a target or budget | Partition Equal Subset Sum |
| 3. Unbounded Knapsack | Same, but items can be reused | Coin Change |
| 4. Longest Common Subsequence | Two sequences, compare or transform one into the other | LCS, Edit Distance |
| 5. Palindromic Subsequence | One string, palindrome property, answer built from both ends | Longest Palindromic Subsequence |
| 6. Longest Increasing Subsequence | Best subsequence obeying an ordering rule | LIS, Russian Doll Envelopes |
Now let's take them one at a time: the tell, the template, and the trap.
1. Fibonacci-style: the answer at i comes from positions before i
The tell: "how many ways to reach step n," "max money if you can't take adjacent items," "how many ways to decode." One sequence, and the answer at each position is a simple combination of the answers at one or two earlier positions.
def climb_stairs(n): # LeetCode 70
a, b = 1, 1 # ways to reach steps i-2 and i-1
for _ in range(2, n + 1):
a, b = b, a + b # dp[i] = dp[i-1] + dp[i-2]
return b
House Robber is the same skeleton with a choice baked in: at each house, either skip it or take it plus the best from two houses back. When the recurrence only looks back a fixed number of steps, you rarely need an array at all, two variables do the job, which is why interviewers love asking for the O(1)-space version as a follow-up.
The 2D extension: grid-path problems (Unique Paths, Minimum Path Sum) are Fibonacci-style in two dimensions: each cell's answer comes from the cell above and the cell to the left. Same idea, one more index.
The trap: counting problems ("how many ways") versus optimization problems ("max profit") use the same recurrence shape but different combine operations, + versus max. Say out loud which one you're doing; muddling them is the most common Fibonacci-family bug.
Learn it from: Climbing Stairs, House Robber, Decode Ways, Unique Paths, Minimum Path Sum.
2. 0/1 Knapsack: pick each item once, hit a budget
The tell: you have a collection of items with sizes (or weights, or values), each usable at most once, and you must hit a target sum, fill a capacity, or split the collection. The words subset, partition, and target are flashing signs.
def can_partition(nums): # LeetCode 416
target, rem = divmod(sum(nums), 2)
if rem:
return False
dp = [True] + [False] * target # dp[s]: can some subset sum to s?
for x in nums:
for s in range(target, x - 1, -1): # backwards: each item used once
dp[s] = dp[s] or dp[s - x]
return dp[target]
The trap is that inner loop direction. Iterating the sums backwards guarantees each item is counted once; iterate forwards and you have silently allowed reuse, which turns this into the next pattern and produces wrong answers that pass small test cases. If an interviewer asks you "why backwards?", this is the answer they want: going right to left means dp[s - x] still refers to the state before this item was considered.
Learn it from: Subset Sum, Partition Equal Subset Sum, Target Sum, Last Stone Weight II.
3. Unbounded Knapsack: same game, unlimited supply
The tell: identical setup, except each item can be used any number of times. Coins, ropes to cut, tasks to repeat. If you can take another copy of something you already took, you are here.
def coin_change(coins, amount): # LeetCode 322
NO = float('inf')
dp = [0] + [NO] * amount # dp[a]: fewest coins to make amount a
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[amount] if dp[amount] != NO else -1
Notice how little changed from 0/1: the loop structure allows an item to contribute repeatedly. That is the entire difference between the two knapsack patterns, and being able to say that difference in one sentence is worth more in an interview than solving ten extra random problems.
The trap: combinations versus permutations. Coin Change II ("how many ways to make the amount") gives different answers depending on whether the item loop is outside the amount loop or inside it. Outside counts combinations; inside counts ordered sequences. Interviewers use this exact distinction to probe whether you understand your own table.
Learn it from: Coin Change, Coin Change II, Rod Cutting, Perfect Squares.
Want each of these taught as a full chapter? Grokking Dynamic Programming is our dedicated DP course: it builds each pattern from brute force to memoization to bottom-up, one variation at a time, with runnable solutions. If you want DP in the context of all the other interview patterns, it's also covered inside Grokking the Coding Interview.
4. Longest Common Subsequence: two sequences, match or don't
The tell: the problem hands you two strings or arrays and asks you to compare, align, or transform one into the other. Longest common anything, edit distance, minimum deletions to make equal.
def lcs(a, b): # LeetCode 1143
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]: # match: extend the diagonal
dp[i][j] = dp[i - 1][j - 1] + 1
else: # no match: drop a char from one side
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
The 2D table reads as "best answer using the first i characters of a and the first j characters of b." Every problem in this family is that table with a different cell rule. Edit Distance adds a third option (replace) to the same skeleton. Once you see the table, half a dozen "hard" string problems become fill-in-the-cell-rule exercises.
The trap: off-by-one indexing between the string (0-based) and the table (1-based, because row 0 means "empty prefix"). Write a[i - 1] deliberately and say why. Fumbling the boundary rows under pressure is how candidates lose ten minutes they don't have.
Learn it from: Longest Common Subsequence, Edit Distance, Delete Operation for Two Strings, Shortest Common Supersequence.
5. Palindromic Subsequence: one string, both ends inward
The tell: one string, and the word palindrome. Because palindromes are defined by their two ends matching, the subproblems are intervals [i, j], and answers for short intervals build answers for longer ones.
def longest_palindromic_subseq(s): # LeetCode 516
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1 # a single char is a palindrome
for j in range(i + 1, n):
if s[i] == s[j]: # ends match: wrap the inside
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
The trap: substring versus subsequence. A palindromic substring must be contiguous, a subsequence need not be. The interval-DP skeleton serves both, but the cell rule changes, and interviewers deliberately pick the one you didn't practice. Check which word the problem uses before you write a line.
Learn it from: Longest Palindromic Subsequence, Longest Palindromic Substring, Palindromic Substrings (count), Minimum Insertions to Make a String Palindrome.
6. Longest Increasing Subsequence: best chain ending here
The tell: find the longest or best subsequence that obeys an ordering rule: strictly increasing numbers, envelopes that nest, jobs that don't overlap. The state is "the best chain ending at element i."
def length_of_lis(nums): # LeetCode 300
dp = [1] * len(nums) # dp[i]: longest chain ending at i
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp, default=0)
This is O(n²), and for most interviews, arriving at it cleanly with a clear explanation is a pass. The O(n log n) upgrade (patience sorting with binary search) is a great follow-up to mention by name; offer it, and write it only if asked.
The trap: LIS problems love hiding behind a sort. Russian Doll Envelopes is LIS after sorting by width ascending and height descending, and that second sort key is the entire problem. When a 2D ordering problem stalls, ask: "what sort makes this one-dimensional?"
Learn it from: Longest Increasing Subsequence, Maximum Sum Increasing Subsequence, Russian Doll Envelopes, Number of Longest Increasing Subsequences.
Diagnosing a DP problem in 30 seconds
When a problem smells like DP (maximize, minimize, count the ways, and greedy has no proof), run the tells in order:
- How many sequences? Two sequences: LCS family. One string plus the word palindrome: palindromic family.
- Are you picking items against a budget or target? Once each: 0/1 knapsack. Reusable: unbounded knapsack.
- Is the answer built position by position from a few previous positions? Fibonacci-style.
- Is the answer the best chain or subsequence under an ordering rule? LIS.
Say the diagnosis out loud in the interview: "two strings, compare and transform, so this looks like the LCS family; the state should be prefixes of both." That single sentence tells the interviewer you have a method, not luck. It's the same narration skill that separates candidates at every level.
Memoization or tabulation?
Both are fine in interviews, and arguing about it wastes time you need. My advice, and how we teach it: discover the recurrence top-down (write the brute-force recursion, add a cache), because that matches how humans actually think about choices. Then, if the interviewer asks for it or the constraints demand it, convert to bottom-up for tight space control, like the two-variable Fibonacci or the 1D knapsack rows above. Saying "I'll memoize first, then flatten it if we need O(1) space" is a perfectly senior answer.
In Python, top-down is almost free: slap @functools.cache on the recursive function and you have a memoized solution while other candidates are still allocating tables. More Python-specific tooling like this is in our Python patterns guide.
How to practice: ~30 problems, not 100
Learn the patterns in the order above; each builds intuition for the next. Do four to six problems per pattern, in increasing difficulty, and after each one write the tell in your own words. That's roughly 30 problems for command of the entire topic, which beats 100 solved at random, retained for a week, and feared forever. If you're working inside a broader plan, DP slots into weeks three and four of our 4-week study plan.
The takeaway
Dynamic programming is six patterns wearing fifty costumes. Fibonacci-style builds position by position. The two knapsacks pick items against a budget, once or repeatedly. LCS aligns two sequences. Palindromic subsequence works intervals from both ends. LIS grows the best chain ending at each element. Learn six tells, six templates, six traps, and the topic that ends most candidates' interviews becomes the place you pull ahead. The full pattern map, DP included, lives in our complete guide to LeetCode patterns.
Ready to actually grok DP? Grokking Dynamic Programming teaches every pattern in this guide from brute force to optimized, one variation at a time. Prefer everything in one place? Grokking the Coding Interview covers all 42 patterns (32 common + 10 advanced) with 300+ problems in six languages for a one-time $79.
FAQs
Is dynamic programming really asked at FAANG interviews? Yes, though unevenly. Google asks DP regularly, Meta and Amazon somewhat less, and almost every company's senior loops reach for it when they want to see how you handle a problem you can't pattern-match instantly. That is precisely why it's worth preparing: it appears exactly when the stakes are highest.
Should I use memoization or tabulation in the interview? Whichever gets you to a correct solution fastest, which for most people is top-down memoization. Interviewers accept both. Mention that you can convert to bottom-up for space optimization; being able to flatten a memoized solution to O(1) space, like the two-variable Fibonacci, is the part that impresses.
How many DP problems should I solve? About 30, if they're organized by pattern: four to six per pattern, in rising difficulty. Random-order grinding is why people solve 100 DP problems and still fear the topic; the problems never get filed under a reusable shape.
How do I know a problem is DP and not greedy? Try to break the greedy choice: if you can construct any input where the locally best pick leads to a globally wrong answer, you need DP. If you can't break it, say so and go greedy (interval scheduling, for example, is greedy, not DP). Interviewers respect a candidate who tests greedy first; it shows the decision was reasoned, not reflexive.
Does Grokking the Coding Interview cover dynamic programming? Yes. DP patterns are part of its 42-pattern curriculum, taught the same way as this guide: tell, template, escalating variations. For a deeper, dedicated treatment, Grokking Dynamic Programming expands each family into its own chapter with many more worked problems.