Ask a room of engineers which interview topic they fear most and dynamic programming wins every time. DP problems look unpredictable, the recurrences feel like magic, and grinding random LeetCode hards rarely helps. Here is the truth that experienced interviewers already know: the vast majority of DP questions asked in 2026 are variations of just five underlying patterns. Learn to recognize the pattern, and the “magic” becomes a repeatable process.
This guide gives you a decision framework for spotting DP problems, walks through the five core patterns with representative problems, and closes with a two-week practice plan you can start today.
How to Recognize a DP Problem in the First 60 Seconds
Before any pattern matching, confirm you are actually looking at a DP problem. Two signals must both be present:
Optimal substructure — the answer to the full problem can be composed from answers to smaller versions of the same problem. Overlapping subproblems — a naive recursion would solve the same smaller versions repeatedly.
In interview language, listen for phrases like “maximum profit,” “minimum cost,” “number of ways,” “longest,” or “can you reach/partition.” Counting and optimization questions over sequences, grids, or choices are DP territory. If each subproblem is solved only once with no overlap, you likely want divide and conquer or greedy instead — saying that distinction out loud earns real credit with interviewers.
Memoization vs. Tabulation: Pick Your Default
Top-down (memoization) means writing the natural recursion first, then caching results. Bottom-up (tabulation) means filling a table iteratively from base cases. Under interview pressure, top-down is the safer default: the recursion mirrors how you reasoned about the problem, and adding a cache is a two-line change. Once it works, offer to convert to bottom-up and discuss the space optimization — many 1D and 2D DP tables can be reduced to two rows or two variables. That conversion is exactly the kind of follow-up senior interviewers use to separate levels.
The 5 DP Patterns That Cover Most Interview Questions
1. Linear Sequence DP (Fibonacci-style)
The state depends on one index moving through a sequence: dp[i] answers the question for the first i elements. Classic problems: Climbing Stairs, House Robber, Maximum Subarray, Decode Ways. The recurrence usually looks at a constant number of previous states, e.g. House Robber’s dp[i] = max(dp[i-1], dp[i-2] + nums[i]). If you can phrase the problem as “best answer ending at (or up to) position i,” you are here. Time is almost always O(n), and space usually collapses to O(1).
2. Grid Path DP
The state is a cell: dp[r][c] is the best answer reaching row r, column c, with movement typically restricted to right/down. Classic problems: Unique Paths, Minimum Path Sum, Maximal Square. The recurrence combines the cell above and the cell to the left. Watch the edges — first row and first column are your base cases, and off-by-one errors here are the most common interview bug.
3. Knapsack (Choice) DP
Each item presents a take-it-or-leave-it decision under a capacity constraint. State: dp[i][w] — best value using the first i items with capacity w. Classic problems: 0/1 Knapsack, Partition Equal Subset Sum, Target Sum, Coin Change (the unbounded variant). The crucial detail interviewers probe: in 0/1 knapsack you iterate capacity backwards when compressing to 1D so each item is used once; in unbounded knapsack you iterate forwards. Explaining why is a strong signal.
4. Longest Common Subsequence (Two-Sequence) DP
The state compares prefixes of two strings or arrays: dp[i][j]. Classic problems: LCS, Edit Distance, Longest Palindromic Subsequence (a string against its reverse), Interleaving String. The recurrence branches on whether the current characters match. Edit Distance in particular remains a favorite at Google and Meta because the three-way minimum (insert, delete, replace) tests whether you truly understand state transitions rather than memorizing code.
5. Interval DP
The state is a range: dp[i][j] answers the question for the subarray between i and j, built up from smaller intervals. Classic problems: Burst Balloons, Matrix Chain Multiplication, Palindrome Partitioning II. These are the hardest of the five — the key move is iterating by interval length and choosing a split point k inside each interval. If a problem asks about merging, bursting, or partitioning a contiguous range, think interval DP before anything else.
A 4-Step Framework to Run in Every DP Interview
Step 1 — Define the state precisely. Say it in one sentence: “dp[i][w] is the maximum value using the first i items with capacity w.” If you cannot phrase the state in one sentence, you do not have the right state yet.
Step 2 — Write the recurrence from the last decision. Ask “what choices exist at the final step?” and express the answer in terms of smaller states.
Step 3 — Nail base cases and iteration order. Base cases come from the smallest valid inputs; iteration order must guarantee every state you read is already computed.
Step 4 — State complexity, then optimize. Complexity is (number of states) × (work per state). Offer the space optimization before the interviewer asks.
Narrate all four steps out loud. Interviewers at every major company grade DP questions on process, and a candidate who structures the derivation cleanly often scores better than one who silently produces a working solution.
Common DP Mistakes That Cost Offers
Jumping to a table before defining the state in words. Confusing subsequence (not contiguous) with substring (contiguous). Forgetting to handle empty inputs in base cases. Memorizing solutions instead of derivations — interviewers routinely add a twist precisely to catch memorizers. And giving up on the brute-force recursion: a correct exponential solution plus a clear memoization plan is worth far more than a broken “optimal” one.
Your 2-Week DP Practice Plan
Days 1–3: Linear sequence. Climbing Stairs, House Robber, Maximum Subarray, Decode Ways. Solve each top-down first, then convert to bottom-up with O(1) space.
Days 4–5: Grid paths. Unique Paths, Minimum Path Sum, Maximal Square.
Days 6–8: Knapsack. Partition Equal Subset Sum, Coin Change, Target Sum. Practice explaining the backwards-iteration trick.
Days 9–11: Two sequences. Longest Common Subsequence, Edit Distance, Longest Palindromic Subsequence.
Days 12–13: Intervals. Matrix Chain Multiplication, Burst Balloons. Expect these to take longer — that is normal.
Day 14: Mixed review. Pick five problems you have not seen, classify each into a pattern within two minutes, and derive the state before writing any code. Classification speed is the skill that transfers to the real interview.
Start Practicing Today
Dynamic programming stops being intimidating the moment you treat it as five patterns plus one derivation framework instead of an endless sea of tricks. Block out the next two weeks, follow the plan above, and practice narrating your state and recurrence out loud — ideally in realistic mock-interview conditions, the way platforms like Niraswa AI help candidates do. Your next DP question won’t be an ambush; it will be a pattern you have already solved a dozen times.
