15 must solve dynamic programming problems

What's the minimum number of dynamic programming problems interview candidates actually need? The answer isn't 50, and it isn't "as many as you can." It's 15, if you pick the right ones.

Why picking DP problems matters more than volume

LeetCode's DP tag has over 500 problems. Most engineers scroll through it, sort by acceptance rate or frequency, and start solving whatever catches their eye. After 40 or 50 problems, they've built deep familiarity with 2-3 pattern families and almost zero exposure to the rest.

That's how you end up confidently solving any Coin Change variant but blanking on a Longest Increasing Subsequence problem that uses a completely different recurrence.

Dynamic programming problems fall into 10 distinct pattern families. Covering one foundational problem per pattern gives wider preparation than solving 50 random problems, because each pattern teaches a different recurrence that transfers to dozens of variations. The selection criterion for this list isn't difficulty or popularity. It's pattern coverage. Every problem was chosen because it's the clearest teaching example for its family and the transition logic generalises to harder variations.

One thing worth knowing: if you map LeetCode's DP tag to pattern families, over 60% of those 500 problems fall into just 3 categories (linear DP, grid DP, and coin change variants). The remaining 7 families are underrepresented in most practice sets. A curated list corrects that imbalance.

The DP problems interview candidates should start with

Each problem below belongs to one of the 10 DP pattern families. Within each family, problems go from foundational to hard. The pattern descriptions link to our coverage of invariants and identification triggers in the DP patterns article.

(1-2). Linear DP

Calculate factorial is the simplest possible recurrence: f(n) = n * f(n-1). You aren't solving this for the math. You're solving it to internalise the DP skeleton of defining a state, writing the recurrence, and identifying the base case. Every harder problem on this list follows that same process.

Nth fibonacci number adds one concept: overlapping subproblems. The naive recursive tree makes the redundant computation visible. This is where you first see why memoization or tabulation matters. If you can't explain why computing fib(5) redundantly computes fib(3) twice, you don't understand DP yet.

(3-4). Coin change

Coin change is the canonical "minimum operations to reach a target" problem. You define dp[amount] as the minimum coins needed, then for each coin you take the minimum of the current value and dp[amount - coin] + 1. This recurrence appears in at least a dozen interview problems across Amazon, Google, and Meta.

The Coin Change recurrence traced for amount = 5 with coins [1, 2, 5]:

Coin change II asks the same question with a twist: count the number of ways instead of the minimum. The subtle difference in how you iterate (specifically the order of your loops) separates "minimum" DP from "count" DP. Getting both right builds the instinct for recognising which variant you're facing.

(5-8). LCS, LIS, and Edit distance

Longest common subsequence is your first two-dimensional DP problem. You define dp[i][j] as the LCS length for the first i characters of one string and the first j characters of the other. The 2D table and the match/no-match branching logic are the foundation for three other problems on this list: edit distance, shortest common supersequence, and interleaving. Mastering LCS first means those later problems feel like variations on a theme rather than entirely new challenges. That compounding effect is exactly why the ordering on this list matters.

Longest increasing subsequence teaches a fundamentally different recurrence shape. Instead of "current state depends on the previous state," it's "current state depends on all previous states that satisfy a condition." The O(n^2) solution makes this dependency visible. Once you see this shape, you'll recognise it in longest bitonic subsequence, largest sum ascending subsequence, and a range of Amazon interview problems.

The patience sorting analogy for LIS isn't just a metaphor. The O(n log n) optimisation literally works by maintaining sorted piles, and understanding why that works gives you a transferable insight about how monotonic approaches can optimise DP.

Edit distance involves three operations (insert, delete, replace), two strings, and one 2D table. The state definition is identical to LCS, but the transition handles three choices instead of two. This problem appears in interviews at Google, Amazon, and Microsoft with surprising regularity.

Wildcard pattern matching builds on edit distance by replacing character operations with pattern-matching rules where ? matches one character and * matches any sequence. The recurrence is similar but the transition logic differs.

Solving this after edit distance forces you to distinguish between problems that look the same but have different invariants. That distinction, recognising when a familiar-looking recurrence needs a different invariant, is one of the more valuable skills DP practice can develop. It's also hard to build by grinding random problems, because you need to solve structurally similar problems back-to-back to notice the differences.

These first eight problems cover six of the ten pattern families.

Completing the pattern coverage

The remaining seven problems fill four more families.

(9-10). Subset sum and knapsack

Subset sum asks whether you can select elements from an array that sum to a target. The boolean DP table here teaches a different state type, where dp[i][s] is true or false rather than a count or minimum. This is the gateway to the entire knapsack family. Zero one knapsack extends that foundation from "is it possible?" to "what's the maximum value?" The inclusion/exclusion decision at each item is the core mechanic, and Amazon tests knapsack-family problems more frequently than almost any other DP category.

(11-15). Game theory, grid, interval, and string DP

Optimal game strategy is the most conceptually distinct problem on the list. Two players alternate turns, each playing optimally. The recurrence models both players' decisions. The state transition isn't just "what's best for me" but "what's best for me given that my opponent will also play optimally." This is a completely different recurrence shape from everything else here, and it catches engineers off guard precisely because the two-player alternating model doesn't resemble any other DP family.

Destination path count and Largest square area cover grid DP. Destination Path Count gives you the base mechanics, counting paths from top-left to bottom-right where each cell depends only on the cell above and to its left.

Largest square area then shows that grid DP isn't always about paths. The state definition (dp[i][j] = side length of the largest square ending at position i,j) and the min(top, left, diagonal) + 1 transition are non-obvious. Grid DP shows up frequently in Amazon and Google interviews.

Boolean parenthesization asks how many ways you can parenthesise a boolean expression to make it evaluate to true. The interval DP approach, where dp[i][j] represents a subrange of the expression, is the hardest recurrence shape on this list. It's also the least common in actual interviews, but when it does appear, engineers who haven't seen the pattern have almost no chance of deriving it under time pressure.

Word break asks whether a string can be segmented into dictionary words. The recurrence iterates over all possible split points, checking whether a prefix is valid and the remainder has already been solved. This pattern combines string processing with DP in a way that doesn't fit neatly into any of the above families, which is exactly why it's on the list. Google, Amazon, Meta, and Apple all ask it. Together, problems 9 through 15 complete the remaining four pattern families and give you the full ten-family coverage.

How to work through these problems for interview readiness

Don't solve these 1 through 15 in a single sitting. The ordering within each pattern family matters more than the numbering.

Round 1

Covers the foundational shape (problems 1-2). Get the DP skeleton into muscle memory. If you're already comfortable with basic recursion and memoization vs tabulation, you can move through these quickly.

Round 2

Covers the core patterns (problems 3-6, 9, 12), one problem per major pattern family. Don't move to the next pattern until you can write the recurrence from memory and explain why it's correct. The goal here isn't speed. It's recognition across different recurrence shapes.

Round 3

Covers extensions and hard variants (problems 7-8, 10-11, 13-15). These build on Round 2: edit distance extends LCS, knapsack extends subset sum, and wildcard matching extends edit distance. If you've genuinely internalised the Round 2 recurrences, these extensions feel like natural progressions rather than new problems.

What each problem teaches that the others don't

The 15-problem count isn't arbitrary. Each problem introduces at least one concept that doesn't appear elsewhere on the list. The table below maps every problem to the specific concept it uniquely contributes. If you're tempted to trim the list, this table shows you exactly what you'd lose.

Remove any single problem, and you lose coverage of that concept. Add a 16th, and it overlaps with something already on the list. That's the zero-redundancy selection criterion.

Where to go from here

This list gives you the problems. It doesn't teach you the pattern invariants or how to recognise which pattern a new problem belongs to. For that, see our coverage of the 10 DP patterns and their identification triggers. For the full picture on dynamic programming, including recurrence derivation from first principles and proof of correctness, see the complete DP guide. All 15 problems on this list appear in Codeintuition's Dynamic Programming course, which covers 38 problems across these pattern families. The course adds the reasoning layer that a problem list can't provide on its own: why each recurrence works, how to derive it from the problem constraints, and when the pattern applies to a problem you haven't seen before.

If you want to test whether you've actually internalised these patterns or just memorised the solutions, Codeintuition's learning path includes timed assessments that strip away problem names and pattern labels. You get 50 minutes and a problem set calibrated to your performance.

Six months from now, you'll open a DP problem in an interview and the recurrence will click before you finish reading the constraints. You won't have seen that exact problem. You'll just recognise the shape. You can start with the free courses to test whether the approach fits before committing to the full DP sequence.