SpaceComplexity

Top 11 Dynamic Programming Problems to Master for Coding Interviews

May 29, 202611 min read
dsaalgorithmsinterview-prepdynamic-programming
Top 11 Dynamic Programming Problems to Master for Coding Interviews
TL;DR
  • Knapsack direction is the only switch: iterate low-to-high for unbounded (coin change), high-to-low for 0/1 (partition sum); the wrong direction gives a silent wrong answer
  • Two rolling variables replace the full table any time the recurrence looks back at most two states, covering climbing stairs, house robber, and most stock trading variants
  • The LCS 2D table is the template for all dual-sequence DP; edit distance uses the same grid with a three-way recurrence and a diagonal variable to avoid overwrite bugs
  • State machine DP: define states before writing transitions; all six stock trading LeetCode problems share this frame with different rules
  • Interval DP escapes tangled subproblems by asking which operation is last rather than first, unlocking burst balloons, matrix chain, and strange printer
  • Pattern recognition transfers: these 11 problems map to every DP shape interviewers test; the goal is recognizing the frame in a new problem, not recalling the solution

Dynamic programming shows up in roughly 20% of coding interview rounds at top tech companies. The gap is not knowing DP exists. It is recognizing which flavor you are looking at fast enough to act on it, without confusing coin change (unbounded knapsack) with partition sum (0/1 knapsack) when the adrenaline hits mid-interview.

These 11 dynamic programming interview problems cover every DP pattern interviewers actually test. Work through them in order. By the end you will have a mental library that transfers to problems you have never seen. Transfer is the point.

If you want a primer on identifying whether a problem even calls for DP, read when to use dynamic programming first.

Dynamic Programming Interview Problems at a Glance

#ProblemPatternLeetCode
1Climbing StairsLinear 1D, Fibonacci recurrence70
2House RobberAdjacency constraint198
3Coin ChangeUnbounded knapsack322
4Longest Increasing Subsequence1D, scan all previous states300
5Partition Equal Subset SumBoolean 0/1 knapsack416
6Longest Common SubsequenceDual-sequence 2D1143
7Unique PathsGrid counting62
8Word Break1D with substring membership139
9Edit Distance2D, three-way recurrence72
10Buy and Sell Stock with CooldownState machine309
11Burst BalloonsInterval DP312

1. Climbing Stairs: Learn the Recurrence, Not the Answer

You can climb 1 or 2 steps at a time. How many ways to reach step n?

The mistake is trying to enumerate paths. You will enumerate yourself into a corner. The right question is "which states lead to state n?" You arrived at n from either n-1 (one step) or n-2 (two steps). So ways(n) = ways(n-1) + ways(n-2). That is the Fibonacci recurrence, but the derivation matters more than recognizing the name.

def climbStairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Every DP problem answers the same question: what choices lead to this state? This one makes the answer obvious so you learn the method before the problems get hard.

2. House Robber: Every Adjacency Constraint Looks Like This

You can not rob two adjacent houses. At each index, choose to rob (add the current value to dp[i-2]) or skip (carry dp[i-1]).

def rob(nums: list[int]) -> int:
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

The adjacency constraint pattern appears disguised as stock trading cooldown windows, board game movement rules, and grid DP with forbidden neighbors. House Robber II (LC 213) adds a circular array. The fix is running the linear version twice: once excluding the first house, once excluding the last, then taking the max. Classic "one problem, two sub-problems, take the max" energy.

Two-option recurrences reduce cleanly to two rolling variables. Whenever you see O(1) space DP, it is usually this shape.

3. Coin Change: The Knapsack Direction Trap

Given coin denominations and a target amount, find the minimum number of coins. This is the problem that trips people who conflate two different knapsack variants. No warning, no compiler error. Just a wrong answer and a confused interviewer.

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Iterating capacity low-to-high means each coin can be used multiple times. Flip to high-to-low and each item can be used at most once. The loop direction is the only difference between unbounded and 0/1 knapsack. Getting it wrong is silent: the code runs, produces a wrong answer, and nothing tells you why.

The greedy instinct here is to always grab the largest coin. It fails on denominations like {1, 3, 4} targeting 6: greedy picks 4+1+1 = 3 coins, DP picks 3+3 = 2. See greedy vs dynamic programming for the formal proof.

Interviewer asks to draw a triangle pattern. Candidate's solution: print(""), print(""), print(""), print("****"), print("*****").

"Dynamic programming" in action. Some patterns do not need a recurrence, they need a loop. Most DP problems are the opposite.

4. Longest Increasing Subsequence: Not All 1D DP Is Two-State

dp[i] = length of the longest strictly increasing subsequence ending at index i.

def lengthOfLIS(nums: list[int]) -> int:
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Each state depends on all previous states, not just one or two. That is still O(n²) overall. The O(n log n) patience-sorting variant exists, but in a 45-minute interview, name it and code the simpler version first. Getting the O(n log n) wrong under pressure is worse than cleanly delivering the O(n²).

5. Partition Equal Subset Sum: Knapsack With a Boolean Value

Can you split the array into two subsets with equal sums? Target is total // 2. The DP value is boolean: can we reach this sum using a subset of elements seen so far?

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = {0}
    for n in nums:
        dp = dp | {s + n for s in dp}
    return target in dp

The canonical array version must iterate capacity high-to-low to prevent reusing the same element twice. The set comprehension above builds a fresh set each iteration so the direction issue disappears, but know why the array version requires it.

Subset Sum (LC 416), Target Sum (LC 494), and Partition Equal Subset Sum are all the same 0/1 knapsack problem with different objective functions. Learn one, get all three.

6. Longest Common Subsequence: The 2D Template Every String Problem Uses

dp[i][j] = length of the LCS of text1[:i] and text2[:j].

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

When characters match, extend the diagonal. When they do not, take the best of skipping either character. Edit Distance (problem 9) uses the same m×n table but with a three-way recurrence. Learn LCS first because it exposes the 2D structure without the extra complexity.

Any problem involving two sequences usually wants a table indexed by position in each. Row and column base cases (zero-length prefix) are always zeros for counting problems.

7. Unique Paths: Grid DP and the Rolling Array

An m×n grid. Robot starts top-left, can only move right or down. Count distinct paths to the bottom-right corner.

def uniquePaths(m: int, n: int) -> int:
    dp = [1] * n
    for _ in range(m - 1):
        for j in range(1, n):
            dp[j] += dp[j-1]
    return dp[-1]

Each cell = paths from above + paths from the left. The top row and left column are all 1. Because you only look up and left, the full 2D table collapses to a 1D rolling array. See it here so it is familiar when Edit Distance needs it.

8. Word Break: When the Transition Checks a Substring

Can you segment a string using words from a dictionary? dp[i] is True if s[:i] can be built from dictionary words.

def wordBreak(s: str, wordDict: list[str]) -> bool:
    words = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]

dp[0] = True is the base case: the empty string is always segmentable. Without it, nothing propagates forward. This is the most common Word Break bug. It is also the most embarrassing one to explain during debrief.

The structure is identical to Coin Change: iterate positions, try all transitions, check feasibility. Recognizing that both problems share the same frame is the whole point of learning patterns over solutions.

9. Edit Distance: The Hardest 2D String DP Problem

Minimum edit operations (insert, delete, replace) to transform word1 into word2. Three choices per cell. One misread recurrence and you spend ten minutes wondering why "horse" to "ros" gives you 4 instead of 3.

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j-1])
            prev = temp
    return dp[n]

Characters match: free extension from the diagonal. Characters differ: 1 + min(replace=diagonal, delete=above, insert=left).

The rolling array here requires a prev variable to capture the diagonal before the outer loop overwrites it. Write the 2D version first, optimize to 1D only if asked. Do not heroically write the optimized version from scratch under pressure.

10. Stock with Cooldown: Name Your States First

You can buy, sell, and hold a stock, but after selling you must wait one day. Three states: holding (own a stock), sold (just sold, in cooldown), idle (no stock, not in cooldown).

def maxProfit(prices: list[int]) -> int:
    hold, sold, idle = -float('inf'), 0, 0
    for price in prices:
        hold, sold, idle = (
            max(hold, idle - price),
            hold + price,
            max(idle, sold),
        )
    return max(sold, idle)

Define the states first, then write each transition. From idle you can buy (move to hold) or stay. From hold you can sell (move to sold) or stay. From sold you can only move to idle. The transitions are the code.

This is the entry point for all six LeetCode stock trading problems (LC 121, 122, 123, 188, 309, 714). The state machine frame does not change. Only the transition rules do.

11. Burst Balloons: The Last-Operation Inversion

Burst all balloons to maximize coins. Coins from bursting balloon i: nums[left] * nums[i] * nums[right] where left and right are the neighbors still standing.

The trap: thinking about which balloon to burst first creates subproblems that are not independent. Bursting balloon i changes the neighbors of i-1 and i+1. Your beautifully recursive solution falls apart the moment you realize you cannot compute the sub-answers without knowing what else is still standing.

Flip the frame. Ask which balloon is the last to burst in range [left, right]. When k is the last balloon burst in that range, its neighbors are the range boundaries, which are fixed. Everything inside splits into two independent subproblems.

def maxCoins(nums: list[int]) -> int:
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(0, n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + nums[left] * nums[k] * nums[right] + dp[k][right]
                )
    return dp[0][n-1]

The outer loop iterates by length, not by left index. Smaller intervals must be solved before larger ones.

The same reframe solves Matrix Chain Multiplication and Strange Printer (LC 664). Once you see the trick, you recognize the setup in new problems.

How to Actually Use These 11

Work through them in order. After each problem: close the solution, open a blank editor, and solve it again from memory the next day. When you can reproduce it cleanly without hints, move on.

The pattern library is the goal, not the solutions. When a new problem shows up, ask "which of these 11 frames does it map to?" That recognition is what the interview scores.

You do not need 50 DP problems. You need to own these 11 well enough to code them under pressure.

For practice under real interview conditions, where you have to narrate your state design and recurrence aloud and get rubric-based feedback on your explanation, SpaceComplexity runs voice-based mock sessions that train the part LeetCode grinding cannot reach.

For top-down vs bottom-up tradeoffs, read memoization vs tabulation. For complexity analysis, bottom-up dynamic programming walks through how to read time and space off a DP table.

Further Reading