The short answer
Dynamic programming interview questions reduce to 10 recurring patterns: Fibonacci / Climbing Stairs, 0/1 Knapsack, Unbounded Knapsack, Longest Common Subsequence, Longest Increasing Subsequence, Edit Distance, Matrix Chain Multiplication, Palindromic Subsequence, Grid Traversal, and Interval DP. Learn the recurrence for each pattern and you can solve 80 percent of DP problems on LeetCode and HackerRank without memorizing specific solutions.
Dynamic programming scares most candidates in coding interviews. The reality is that 80 percent of DP questions follow one of 10 patterns. If you learn the recurrence relation for each pattern and recognize the problem shape, you can solve new problems in the interview without ever having seen them before. This guide walks through all 10 patterns with the recurrence, a representative problem, and when to recognize each one.
Pattern 1: Fibonacci / Climbing Stairs
The simplest DP pattern. Each state depends on the previous one or two states. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Recognize when: the problem asks how many ways to reach state i and each step can advance 1 or 2 positions.
Representative problems: Climbing Stairs (LeetCode 70), House Robber (LeetCode 198), Decode Ways (LeetCode 91), Min Cost Climbing Stairs (LeetCode 746).
def climb_stairs(n):
if n <= 2: return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return bPattern 2: 0/1 Knapsack
You have a set of items each with a weight and a value. Each item can be picked at most once. Fit items into a knapsack of capacity W to maximize value. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i]] + val[i]). Recognize when: you have a fixed capacity and each item is a yes-or-no decision.
Representative problems: Partition Equal Subset Sum (LeetCode 416), Target Sum (LeetCode 494), Last Stone Weight II (LeetCode 1049), Ones and Zeroes (LeetCode 474).
Pattern 3: Unbounded Knapsack
Same as 0/1 Knapsack but each item can be picked unlimited times. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i][w - wt[i]] + val[i]). The subtle difference: the second term uses dp[i] instead of dp[i-1] because you can reuse item i. Recognize when: items are reusable (coins, cuts of a rod, letters of a repeating alphabet).
Representative problems: Coin Change (LeetCode 322), Coin Change 2 (LeetCode 518), Perfect Squares (LeetCode 279), Word Break (LeetCode 139).
Pattern 4: Longest Common Subsequence (LCS)
Given two sequences, find the longest subsequence that appears in both. Recurrence: if characters match, dp[i][j] = dp[i-1][j-1] + 1, otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Recognize when: two strings or arrays, question asks about matching or shared elements, order must be preserved but elements can be skipped.
Representative problems: Longest Common Subsequence (LeetCode 1143), Shortest Common Supersequence (LeetCode 1092), Delete Operation for Two Strings (LeetCode 583), Distinct Subsequences (LeetCode 115).
Pattern 5: Longest Increasing Subsequence (LIS)
Find the longest subsequence where each element is strictly greater than the previous one. Classical DP recurrence is O(n squared): dp[i] = max(dp[j] + 1 for j in range(i) if nums[j] < nums[i]). The optimal O(n log n) solution uses binary search with a tails array. Recognize when: single array, question about increasing or decreasing ordered subsequence.
Representative problems: Longest Increasing Subsequence (LeetCode 300), Russian Doll Envelopes (LeetCode 354), Number of Longest Increasing Subsequence (LeetCode 673), Longest String Chain (LeetCode 1048).
Pattern 6: Edit Distance
Transform string A into string B using insert, delete, or substitute operations. Recurrence: if characters match, dp[i][j] = dp[i-1][j-1], otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). Recognize when: two strings, question about minimum edits or transformations or matches.
Representative problems: Edit Distance (LeetCode 72), One Edit Distance (LeetCode 161), Minimum ASCII Delete Sum (LeetCode 712), Regex Matching (LeetCode 10).
Pattern 7: Matrix Chain Multiplication
Partition a sequence to minimize or maximize a cost function. Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i, k, j) for k in range(i, j)). Solve diagonally from smallest to largest subrange. Recognize when: question about optimal parenthesization, bursting balloons, or combining intervals.
Representative problems: Matrix Chain Multiplication (classic), Burst Balloons (LeetCode 312), Minimum Cost to Cut a Stick (LeetCode 1547), Strange Printer (LeetCode 664).
Pattern 8: Palindromic Subsequence
Find the longest palindromic subsequence in a string. Recurrence: if first and last characters match, dp[i][j] = dp[i+1][j-1] + 2, otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Solve by filling the DP table along diagonals of increasing length. Recognize when: single string, question about palindromes or symmetric subsequences.
Representative problems: Longest Palindromic Subsequence (LeetCode 516), Longest Palindromic Substring (LeetCode 5), Palindrome Partitioning II (LeetCode 132), Minimum Insertion Steps to Make a Palindrome (LeetCode 1312).
Pattern 9: Grid Traversal
Count paths or find minimum cost in a 2D grid moving only right or down. Recurrence: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] for min-cost variants, or dp[i][j] = dp[i-1][j] + dp[i][j-1] for path-counting variants. Recognize when: 2D grid, movement is restricted to right and down (or similar constraints).
Representative problems: Unique Paths (LeetCode 62), Unique Paths II (LeetCode 63), Minimum Path Sum (LeetCode 64), Dungeon Game (LeetCode 174).
Pattern 10: Interval DP
Solve problems where the state is defined by a range (i, j) and the answer for the full range depends on answers for smaller subranges. Similar shape to Matrix Chain Multiplication but with different cost functions. Recurrence: dp[i][j] = f(dp[i][k], dp[k+1][j]) for k in range(i, j). Recognize when: operation combines two adjacent subranges, and the final result depends on the order of combination.
Representative problems: Merge Stones (LeetCode 1000), Guess Number Higher or Lower II (LeetCode 375), Remove Boxes (LeetCode 546), Predict the Winner (LeetCode 486).
How to practice these patterns
Do not grind problems randomly. For each pattern, pick 5 problems of increasing difficulty and solve them in the same session. Write out the recurrence on paper before coding. Compare your recurrence to the pattern template above. Repeat the next day. After 2 to 3 sessions per pattern you will recognize the shape in new problems immediately.
Order to learn: start with Pattern 1 (easiest recurrence), then 2 and 3 (knapsack family), then 4, 5, 6 (string DP), then 7, 8, 10 (interval variants), then 9 (grid). Budget 2 weeks if you solve 2 hours per day.
Frequently Asked Questions
Do I need to learn all 10 patterns before my interview?
If the interview is more than 3 weeks away, yes. If you have less than 2 weeks, prioritize Patterns 1 through 5. Those five cover roughly 60 to 70 percent of DP questions asked at FAANG and tier-2 companies.
Top-down memoization or bottom-up tabulation: which should I use in interviews?
Top-down memoization is easier to derive from a recursive solution and shows your thinking process. Most interviewers prefer it as a first pass, then ask you to convert to bottom-up for optimization. Lead with top-down, know how to translate to bottom-up on demand.
How do I recognize a DP problem in the first place?
Look for three signals: the problem asks for the optimal (min, max, count, longest, shortest) something, the problem has overlapping subproblems (brute-force recursion would repeat work), and the state space is bounded (you can define a dp table with reasonable dimensions). If all three signals are present, it is almost certainly DP.
What time complexity should I target for DP problems?
Most DP problems have O(states * transitions) complexity. For Patterns 1 through 9, this is usually O(n), O(n squared), or O(n * W) where W is a capacity. If your DP solution is O(n cubed) or worse and the problem looks solvable in less, you may be missing a space or time optimization.
Which pattern does the famous Longest Palindromic Substring problem belong to?
Pattern 8 (Palindromic Subsequence) with a small variant. The standard DP solution uses the same i and j indexing but checks substring palindromicity instead of subsequence membership. Alternatively, you can solve it with expand-around-center in O(n squared) time and O(1) space, which many interviewers prefer for its clarity.
