Top 15 Dynamic Programming Problems and What Each One Teaches

There are hundreds of dynamic programming problems on LeetCode. Maybe fifteen of them teach something genuinely new. The rest are just the same five ideas wearing different hats.

This list has one filter: each problem earns its spot by teaching something no other problem here teaches. Solve all 15 in order and you have a complete curriculum covering every major DP pattern that shows up in real interviews. Skip around and you'll wonder why your Burst Balloons solution is wrong when you understand the concept perfectly. (Spoiler: the concept you understand is not the one the problem is testing.)

This is for engineers who get recursion and memoization but want a complete map before their next interview.

The Foundation

1. Climbing Stairs (LC 70)

What it teaches: The full transformation from recurrence to table to O(1) space.

dp[i] = dp[i-1] + dp[i-2]. The problem takes two minutes to solve. The point isn't the solution. The point is doing the transformation three times: recursive with memoization, then bottom-up table, then two rolling variables.

Every DP problem after this should go through the same three stages. If you can't squeeze Climbing Stairs down to two integers, you'll struggle to apply that trick on LCS or Edit Distance where it actually saves you an interview.

2. Maximum Subarray (LC 53)

What it teaches: Implicit state machines and the all-negative initialization bug.

Kadane's algorithm is DP with a reset. State = maximum subarray ending at index i. Transition: dp[i] = max(nums[i], dp[i-1] + nums[i]). Extend the previous subarray or start fresh.

The bug that matters: initializing best to 0 instead of nums[0]. When all values are negative, the answer is the least negative element. Initialize to 0 and you return 0, which sounds reasonable and is completely wrong.

def maxSubArray(nums):
    best = curr = nums[0]  # not 0
    for n in nums[1:]:
        curr = max(n, curr + n)
        best = max(best, curr)
    return best

Kadane's is so clean that people memorize it without understanding it. Understanding it means you can reconstruct it from scratch when you see Maximum Product Subarray (LC 152) and realize it's the same idea with a twist.

3. House Robber (LC 198)

What it teaches: Two-state DP, where your last decision constrains the current one.

Rob or skip. If you rob house i, you cannot rob i-1. Track two states: rob[i] and skip[i]. Transition: rob[i] = skip[i-1] + nums[i], skip[i] = max(rob[i-1], skip[i-1]).

This pattern repeats in stock problems with cooldowns and task schedulers. Recognizing it here in its simplest form makes it easy to spot later when it's buried inside a harder constraint. It also shows up as problem 15 on this list, which is almost poetic.

Knapsack: Three Problems, Three Distinct Lessons

These look alike from the outside. The internal mechanics are completely different.

4. Coin Change (LC 322)

What it teaches: Unbounded knapsack, where items can be reused.

dp[i] = minimum coins to make amount i. Iterate from low to high. Reusing a coin is allowed, so you want earlier results to count toward later ones. dp[i] = min(dp[i], dp[i - coin] + 1). Initialize dp[0] = 0, everything else to infinity.

The sweep direction is the whole game here. Every knapsack bug you'll ever write in an interview comes down to using the wrong sweep direction because you didn't think clearly about whether reuse is allowed.

5. Partition Equal Subset Sum (LC 416)

What it teaches: 0/1 knapsack, where each item can only be used once.

Can you split the array into two equal-sum subsets? Reframe it: can you find a subset summing to total // 2? Boolean knapsack.

Iterate from high to low: for j in range(target, num - 1, -1): dp[j] |= dp[j - num]. Going backward prevents using the same element twice in one pass. Going forward allows reuse, which accidentally gives you unbounded knapsack.

This direction flip looks cosmetic. It decides whether you solve the problem you intended. Most candidates who get this wrong don't even know they got it wrong, because their solution passes the obvious test cases.

Knapsack sweep direction diagram: forward iteration allows reuse (unbounded), backward prevents it (0/1)

One character changes the problem. Low-to-high lets each coin update future cells in the same pass, so it can be reused. High-to-low reads only from the previous pass, so each item is used at most once.

6. Coin Change II (LC 518)

What it teaches: Counting combinations instead of optimizing a value.

Same structure as Coin Change. But you're counting the number of ways to hit each amount, not minimizing coins. The base case flips: dp[0] = 1 (one way to make 0). Iteration stays low to high for unbounded reuse.

Counting DP uses addition. Optimization DP uses min or max. The state space looks identical. The semantics diverge completely. Confuse them and you get a number that's wrong by several orders of magnitude, which at least makes it easy to spot.

Grid DP

7. Unique Paths (LC 62)

What it teaches: 2D grids and the rolling-row space optimization.

dp[i][j] = paths to cell (i, j) = dp[i-1][j] + dp[i][j-1]. You only need the previous row at any point. Replace the O(mn) table with a single O(n) array updated in place.

Practice this reduction explicitly. Grid DP shows up constantly (minimum path sum, dungeon game, cherry pickup), and the rolling optimization is always available once you see it the first time.

Sequence DP

8. Longest Increasing Subsequence (LC 300)

What it teaches: Using binary search to go from O(n²) DP to O(n log n).

The O(n²) solution is straightforward: dp[i] = length of LIS ending at index i, scan all j < i where nums[j] < nums[i]. This is fine. It's also not fine in an interview where n is large.

The O(n log n) solution is the actual lesson. Maintain a tails array where tails[k] is the smallest tail of any increasing subsequence of length k+1. Binary search for the insertion position on each element. The array doesn't give you the actual subsequence, but it gives you the length.

import bisect

def lengthOfLIS(nums):
    tails = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)
        if pos == len(tails):
            tails.append(n)
        else:
            tails[pos] = n
    return len(tails)

LIS is the go-to example of binary search accelerating DP. The same trick carries to Russian Doll Envelopes (LC 354), which is LIS in two dimensions with a sorting trick on top.

9. Longest Common Subsequence (LC 1143)

What it teaches: The canonical 2D sequence alignment table.

dp[i][j] = LCS of text1[:i] and text2[:j]. Characters match: dp[i][j] = dp[i-1][j-1] + 1. No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

LCS is the foundation for diff tools, DNA alignment, and a cluster of interview variants. Do this before Edit Distance. If you do Edit Distance first you'll confuse yourself trying to figure out which transitions mean what.

10. Edit Distance (LC 72)

What it teaches: Three-way transitions and the full string alignment DP.

Insert, delete, or replace. Characters match: copy the diagonal with no cost. Characters differ: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Edit Distance forces you to understand what each cell in the 2D table actually means. After LCS, where you only had two choices, three choices feels like chaos. Then you draw it out and it clicks. That click is the lesson.

11. Word Break (LC 139)

What it teaches: DP on string positions, not individual characters.

dp[i] = True if text[:i] can be segmented using the dictionary. For each position i, scan backward for a dictionary word ending there. If dp[j] is True and text[j:i] is in the dictionary, set dp[i] = True.

The state isn't a character. It's a position in the string. This reframing recurs in any DP that validates or constructs a sequence prefix by prefix.

12. Decode Ways (LC 91)

What it teaches: Conditional transitions, where guards decide whether a transition applies.

dp[i] = number of ways to decode s[:i]. A single digit (1 through 9, not 0) gives dp[i] += dp[i-1]. Two digits forming [10, 26] give dp[i] += dp[i-2]. Leading zeros kill both transitions.

DP doesn't always offer an unconditional formula. Decode Ways builds the habit of checking validity constraints before applying each transition. This shows up constantly on harder string problems, and candidates who haven't internalized it try to write one clean formula and spend 20 minutes debugging guards.

Interval DP

13. Palindromic Substrings (LC 647)

What it teaches: Two framings for the same problem class.

You can expand from each center (O(n²) time, O(1) space) or build an interval DP table where dp[i][j] = True if s[i..j] is a palindrome. The expansion approach is elegant. It also won't generalize to longest palindromic subsequence (LC 516), which needs the interval table.

Understanding both framings here means the subsequence variant is a direct application rather than a new problem to panic about.

14. Burst Balloons (LC 312)

What it teaches: The last-operation inversion that makes interval DP tractable.

Bursting balloon i gives nums[i-1] * nums[i] * nums[i+1]. Maximize total coins. Sounds straightforward.

The naive framing ("which balloon do I burst first?") creates tangled subproblems because bursting changes the neighbors of everything around it. The correct framing flips the question: which balloon do I burst last in range [i, j]? Last position k gives nums[i-1] * nums[k] * nums[j+1]. The subproblems [i, k-1] and [k+1, j] are now independent, because k is still there while we solve them.

This last-operation inversion is the core technique behind interval DP. The same move appears in matrix chain multiplication and Strange Printer (LC 664). If you do only one interval DP problem, do this one. It's the hardest conceptual shift on this list.

Tree DP

15. House Robber III (LC 337)

What it teaches: DP on trees, where state lives in return values instead of arrays.

The house robber constraint on a binary tree: no parent and child in the same theft. Each DFS call returns a pair: (rob_this_node, skip_this_node). Process children first (postorder), then compute parent states from child results.

def rob(root):
    def dfs(node):
        if not node:
            return 0, 0
        l_rob, l_skip = dfs(node.left)
        r_rob, r_skip = dfs(node.right)
        return node.val + l_skip + r_skip, max(l_rob, l_skip) + max(r_rob, r_skip)
    return max(dfs(root))

Tree DP is DP where the DAG is a tree. Once this clicks, binary tree cameras (LC 968) and diameter of binary tree (LC 543) become direct applications. The pattern is: state is a tuple in the return value, not an array indexed by position.

Quick Reference

#	Problem	Pattern	Key insight
1	Climbing Stairs	1D linear	Recurrence to O(1) space
2	Maximum Subarray	State machine	Init to `nums[0]`, not 0
3	House Robber	2-state linear	Mutually exclusive decisions
4	Coin Change	Unbounded knapsack	Low-to-high sweep
5	Partition Equal Subset	0/1 knapsack	High-to-low sweep
6	Coin Change II	Counting DP	Addition not min/max
7	Unique Paths	2D grid	Rolling row optimization
8	LIS	Sequence + binary search	Patience sort trick
9	LCS	2D alignment	Canonical subsequence DP
10	Edit Distance	3-way alignment	Three choices per cell
11	Word Break	Prefix DP	State = position not character
12	Decode Ways	Conditional transitions	Guards before each transition
13	Palindromic Substrings	Expansion + interval	Two framings, different reach
14	Burst Balloons	Interval DP	Last-operation inversion
15	House Robber III	Tree DP	State lives in return values

What Comes Next

After these 15, you should be able to spot the DP structure of most interview problems in a few minutes. The remaining bottleneck is speed and narration. And narration is the part nobody practices.

If you can't state what dp[i] means in one sentence before touching the keyboard, you don't have the DP yet. SpaceComplexity runs live DP walkthroughs with a voice AI interviewer, so you can practice defining states and transitions out loud before someone's watching.

Two problems that fill the remaining gaps: House Robber with Cooldown (LC 309) for a state machine with a mandatory delay, and Regular Expression Matching (LC 10) for harder conditional transitions with wildcard logic.

For more on recognizing when a problem is DP, see how to recognize dynamic programming problems. For the top-down vs bottom-up decision, see memoization vs tabulation. If you're still deciding between DP and greedy, when to use dynamic programming has the exchange argument test. And if your LeetCode practice isn't translating to interview results, you're practicing LeetCode wrong explains the gap.