Dynamic Programming Problem Set

Dynamic programming problems are won or lost on one sentence: what does dp[i]dp[i] (or dp[i][j]dp[i][j]) actually mean? Every problem below is solvable the moment that sentence is precise — the code is almost always short once the recurrence is right. Work through these in order: the first three build the 1D “look back a couple of steps” habit, the next three move to a second dimension, and the last two combine both string DP and explicit reconstruction of a decision.

How to use this set

Each problem gives you a function stub with a # TODO# TODO and a passpass — running it as-is will fail the sample asserts below it. Edit the stub in place, hit Run, and check your printed output against the # expect# expect comment. Stuck? Open the Show solution panel for the full, annotated fix, its recurrence, and its time/space complexity. When you’re confident, go submit the same idea on the real LeetCode problem linked in each Pattern line — the in-page playground only runs Python’s standard library, so it’s your first check, not the final judge.

1. Climbing Stairs — LC 70 — Easy

Open LC 70 on LeetCode

Pattern: One Dimensional DP

Problem. You’re climbing a staircase with nn steps. Each move you can climb either 1 or 2 steps. Return the number of distinct ways to reach the top.

1 <= n <= 451 <= n <= 45

dp[i] = dp[i-1] + dp[i-2], \quad dp[0] = 1,\ dp[1] = 1

climbing_stairs.py

def climb_stairs(n):
    # TODO: dp[i] = dp[i-1] + dp[i-2], with dp[0] = dp[1] = 1
    pass
 
 
print(climb_stairs(3))   # expect 3
print(climb_stairs(5))   # expect 8

climbing_stairs.py

def climb_stairs(n):
    # TODO: dp[i] = dp[i-1] + dp[i-2], with dp[0] = dp[1] = 1
    pass
 
 
print(climb_stairs(3))   # expect 3
print(climb_stairs(5))   # expect 8

Show solution

climbing_stairs_solution.py

def climb_stairs(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1     # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
 
 
print(climb_stairs(3))   # 3
print(climb_stairs(5))   # 8

climbing_stairs_solution.py

def climb_stairs(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1     # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
 
 
print(climb_stairs(3))   # 3
print(climb_stairs(5))   # 8

Recurrence: reaching step ii means your last hop was 1 step from i - 1i - 1 or 2 steps from i - 2i - 2, so the ways add together — it’s Fibonacci wearing a different costume.

Complexity: Time $O(n)$ , Space $O(1)$ (only the last two values matter).

2. House Robber — LC 198 — Medium

Open LC 198 on LeetCode

Pattern: One Dimensional DP

Problem. Given numsnums representing loot in houses arranged in a row, return the maximum amount you can rob without robbing two adjacent houses.

1 <= len(nums) <= 1001 <= len(nums) <= 100
0 <= nums[i] <= 4000 <= nums[i] <= 400

dp[i] = \max\big(dp[i-1],\ dp[i-2] + nums[i]\big)

house_robber.py

def rob(nums):
    # TODO: at each house, either skip it (carry dp[i-1]) or rob it
    # (dp[i-2] + nums[i])
    pass
 
 
print(rob([1, 2, 3, 1]))       # expect 4
print(rob([2, 7, 9, 3, 1]))    # expect 12

house_robber.py

def rob(nums):
    # TODO: at each house, either skip it (carry dp[i-1]) or rob it
    # (dp[i-2] + nums[i])
    pass
 
 
print(rob([1, 2, 3, 1]))       # expect 4
print(rob([2, 7, 9, 3, 1]))    # expect 12

Show solution

house_robber_solution.py

def rob(nums):
    prev2, prev1 = 0, 0     # dp[i-2], dp[i-1]
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
print(rob([1, 2, 3, 1]))       # 4  (rob house 0 and house 2)
print(rob([2, 7, 9, 3, 1]))    # 12 (rob houses 0, 2, and 4)

house_robber_solution.py

def rob(nums):
    prev2, prev1 = 0, 0     # dp[i-2], dp[i-1]
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
print(rob([1, 2, 3, 1]))       # 4  (rob house 0 and house 2)
print(rob([2, 7, 9, 3, 1]))    # 12 (rob houses 0, 2, and 4)

Recurrence: skipping house ii carries forward dp[i-1]dp[i-1]; robbing it adds nums[i]nums[i] to dp[i-2]dp[i-2] (since i-1i-1 becomes off-limits). Take whichever is bigger.

Complexity: Time $O(n)$ , Space $O(1)$ .

3. Coin Change — LC 322 — Medium

Open LC 322 on LeetCode

Pattern: One Dimensional DP

Problem. Given coin denominations coinscoins and a target amountamount, return the fewest coins needed to make up amountamount. Each coin can be used an unlimited number of times. Return -1-1 if it’s impossible.

1 <= len(coins) <= 121 <= len(coins) <= 12
0 <= amount <= 100000 <= amount <= 10000

dp[i] = \min_{c \in coins,\ c \le i} \big(dp[i-c] + 1\big), \quad dp[0] = 0

coin_change.py

def coin_change(coins, amount):
    # TODO: dp[i] = fewest coins to make amount i, dp[0] = 0.
    # Try every coin c <= i and take the best dp[i - c] + 1.
    pass
 
 
print(coin_change([1, 2, 5], 11))   # expect 3
print(coin_change([2], 3))          # expect -1

coin_change.py

def coin_change(coins, amount):
    # TODO: dp[i] = fewest coins to make amount i, dp[0] = 0.
    # Try every coin c <= i and take the best dp[i - c] + 1.
    pass
 
 
print(coin_change([1, 2, 5], 11))   # expect 3
print(coin_change([2], 3))          # expect -1

Show solution

coin_change_solution.py

def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount   # dp[i] = fewest coins for amount i
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1
 
 
print(coin_change([1, 2, 5], 11))   # 3   (5 + 5 + 1)
print(coin_change([2], 3))          # -1  (can't make an odd amount with only 2s)

coin_change_solution.py

def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount   # dp[i] = fewest coins for amount i
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1
 
 
print(coin_change([1, 2, 5], 11))   # 3   (5 + 5 + 1)
print(coin_change([2], 3))          # -1  (can't make an odd amount with only 2s)

Recurrence: dp[i]dp[i] looks back at every coin cc that fits and takes the cheapest way to reach i - ci - c, then adds one coin. Unlike Coin Change II (counting combinations), the coin loop goes on the inside here because order genuinely doesn’t matter for a minimum.

Complexity: Time $O(\text{amount} \cdot \text{len(coins)})$ , Space $O(\text{amount})$ .

4. Longest Increasing Subsequence — LC 300 — Medium

Open LC 300 on LeetCode

Pattern: Classic DP: LIS, LCS, and Edit Distance

Problem. Given an integer array numsnums, return the length of the longest strictly increasing subsequence (not necessarily contiguous).

1 <= len(nums) <= 25001 <= len(nums) <= 2500

dp[i] = 1 + \max_{\substack{j < i \\ nums[j] < nums[i]}} dp[j] \qquad (dp[i] = 1 \text{ if no such } j \text{ exists})

longest_increasing_subsequence.py

def length_of_lis(nums):
    # TODO: dp[i] = length of the LIS ending exactly at index i.
    # Look back at every j < i with nums[j] < nums[i].
    pass
 
 
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))          # expect 4
print(length_of_lis([0, 1, 0, 3, 2, 3]))  # expect 4

longest_increasing_subsequence.py

def length_of_lis(nums):
    # TODO: dp[i] = length of the LIS ending exactly at index i.
    # Look back at every j < i with nums[j] < nums[i].
    pass
 
 
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))          # expect 4
print(length_of_lis([0, 1, 0, 3, 2, 3]))  # expect 4

Show solution

longest_increasing_subsequence_solution.py

def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n   # dp[i] = length of the LIS ending exactly at index i
 
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)
 
 
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))                 # 4  ([2, 3, 7, 18] or [2, 3, 7, 101])
print(length_of_lis([0, 1, 0, 3, 2, 3]))   # 4  ([0, 1, 2, 3])

longest_increasing_subsequence_solution.py

def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n   # dp[i] = length of the LIS ending exactly at index i
 
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)
 
 
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))                 # 4  ([2, 3, 7, 18] or [2, 3, 7, 101])
print(length_of_lis([0, 1, 0, 3, 2, 3]))   # 4  ([0, 1, 2, 3])

Recurrence: every earlier index jj with a smaller value is a valid predecessor — dp[i]dp[i] takes the best one and adds itself. The answer is max(dp)max(dp) since the LIS can end anywhere, not just at the last index.

Complexity: Time $O(n^2)$ (an $O(n \log n)$ patience-sorting variant exists using bisect_leftbisect_left), Space $O(n)$ .

5. Longest Common Subsequence — LC 1143 — Medium

Open LC 1143 on LeetCode

Pattern: Classic DP: LIS, LCS, and Edit Distance

Problem. Given two strings text1text1 and text2text2, return the length of their longest common subsequence, or 0 if none exists.

1 <= len(text1), len(text2) <= 10001 <= len(text1), len(text2) <= 1000

dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{otherwise} \end{cases}

longest_common_subsequence.py

def longest_common_subsequence(text1, text2):
    # TODO: dp[i][j] = LCS length using the first i chars of text1
    # and the first j chars of text2.
    pass
 
 
print(longest_common_subsequence("abcde", "ace"))   # expect 3
print(longest_common_subsequence("abc", "def"))     # expect 0

longest_common_subsequence.py

def longest_common_subsequence(text1, text2):
    # TODO: dp[i][j] = LCS length using the first i chars of text1
    # and the first j chars of text2.
    pass
 
 
print(longest_common_subsequence("abcde", "ace"))   # expect 3
print(longest_common_subsequence("abc", "def"))     # expect 0

Show solution

longest_common_subsequence_solution.py

def longest_common_subsequence(text1, text2):
    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]
 
 
print(longest_common_subsequence("abcde", "ace"))   # 3  ("ace")
print(longest_common_subsequence("abc", "def"))     # 0  (no shared characters)

longest_common_subsequence_solution.py

def longest_common_subsequence(text1, text2):
    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]
 
 
print(longest_common_subsequence("abcde", "ace"))   # 3  ("ace")
print(longest_common_subsequence("abc", "def"))     # 0  (no shared characters)

Recurrence: matching characters extend the diagonal neighbor by one; a mismatch takes the best of dropping one character from either string. The final table cell dp[m][n]dp[m][n] holds the answer.

Complexity: Time $O(mn)$ , Space $O(mn)$ (rollable to $O(\min(m, n))$ ).

6. Unique Paths — LC 62 — Medium

Open LC 62 on LeetCode

Pattern: DP on Grids and Intervals

Problem. A robot starts at the top-left corner of an m x nm x n grid and can only move down or right. Return the number of distinct paths to the bottom-right corner.

1 <= m, n <= 1001 <= m, n <= 100

dp[i][j] = dp[i-1][j] + dp[i][j-1], \quad dp[0][*] = dp[*][0] = 1

unique_paths.py

def unique_paths(m, n):
    # TODO: dp[i][j] = ways to reach cell (i, j), coming from above
    # or from the left. First row and first column are all 1.
    pass
 
 
print(unique_paths(3, 7))   # expect 28
print(unique_paths(3, 2))   # expect 3

unique_paths.py

def unique_paths(m, n):
    # TODO: dp[i][j] = ways to reach cell (i, j), coming from above
    # or from the left. First row and first column are all 1.
    pass
 
 
print(unique_paths(3, 7))   # expect 28
print(unique_paths(3, 2))   # expect 3

Show solution

unique_paths_solution.py

def unique_paths(m, n):
    dp = [1] * n     # first row: only one way to reach any cell -- go right
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]     # dp[j] currently holds "row above" until updated
    return dp[-1]
 
 
print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3

unique_paths_solution.py

def unique_paths(m, n):
    dp = [1] * n     # first row: only one way to reach any cell -- go right
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]     # dp[j] currently holds "row above" until updated
    return dp[-1]
 
 
print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3

Recurrence: a cell is reached either from directly above or directly to the left, so its path count is the sum of both. The rolling 1D array reuses dp[j]dp[j] as “the row above” until it’s overwritten left-to-right in the current row.

Complexity: Time $O(mn)$ , Space $O(n)$ (rolling one row instead of the full grid).

7. Word Break — LC 139 — Medium

Open LC 139 on LeetCode

Pattern: One Dimensional DP

Problem. Given a string ss and a dictionary of strings word_dictword_dict, return TrueTrue if ss can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.

1 <= len(s) <= 3001 <= len(s) <= 300

dp[i] = \bigvee_{j < i} \big(dp[j] \wedge s[j{:}i] \in \text{dict}\big), \quad dp[0] = \text{True}

word_break.py

def word_break(s, word_dict):
    # TODO: dp[i] = True if s[:i] can be segmented into dictionary words.
    # dp[0] = True (empty prefix). Try every split point j < i.
    pass
 
 
print(word_break("leetcode", ["leet", "code"]))                          # expect True
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))    # expect False

word_break.py

def word_break(s, word_dict):
    # TODO: dp[i] = True if s[:i] can be segmented into dictionary words.
    # dp[0] = True (empty prefix). Try every split point j < i.
    pass
 
 
print(word_break("leetcode", ["leet", "code"]))                          # expect True
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))    # expect False

Show solution

word_break_solution.py

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True     # empty prefix is trivially "breakable"
 
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
 
    return dp[n]
 
 
print(word_break("leetcode", ["leet", "code"]))
# True  ("leet" + "code")
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))
# False (no split covers the whole string)

word_break_solution.py

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True     # empty prefix is trivially "breakable"
 
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
 
    return dp[n]
 
 
print(word_break("leetcode", ["leet", "code"]))
# True  ("leet" + "code")
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))
# False (no split covers the whole string)

Recurrence: dp[i]dp[i] asks “is there some earlier breakable prefix jj such that the piece from jj to ii is a dictionary word?” — exactly one TrueTrue split point is enough.

Complexity: Time $O(n^2)$ (with $O(1)$ average substring/set lookups), Space $O(n)$ .

8. Edit Distance — LC 72 — Medium

Open LC 72 on LeetCode

Pattern: Classic DP: LIS, LCS, and Edit Distance

Problem. Given two strings word1word1 and word2word2, return the minimum number of single-character insert, delete, or replace operations to convert word1word1 into word2word2.

0 <= len(word1), len(word2) <= 5000 <= len(word1), len(word2) <= 500

dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } word1[i-1] = word2[j-1] \\ 1 + \min\big(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]\big) & \text{otherwise} \end{cases}

edit_distance.py

def min_distance(word1, word2):
    # TODO: dp[i][j] = edit distance between word1[:i] and word2[:j].
    # dp[i][0] = i, dp[0][j] = j (all inserts/deletes).
    pass
 
 
print(min_distance("horse", "ros"))              # expect 3
print(min_distance("intention", "execution"))    # expect 5

edit_distance.py

def min_distance(word1, word2):
    # TODO: dp[i][j] = edit distance between word1[:i] and word2[:j].
    # dp[i][0] = i, dp[0][j] = j (all inserts/deletes).
    pass
 
 
print(min_distance("horse", "ros"))              # expect 3
print(min_distance("intention", "execution"))    # expect 5

Show solution

edit_distance_solution.py

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    for i in range(m + 1):
        dp[i][0] = i     # delete all of word1[:i]
    for j in range(n + 1):
        dp[0][j] = j     # insert all of word2[:j]
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]          # characters already match
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],   # replace
                    dp[i - 1][j],       # delete from word1
                    dp[i][j - 1],       # insert into word1
                )
 
    return dp[m][n]
 
 
print(min_distance("horse", "ros"))              # 3
print(min_distance("intention", "execution"))    # 5

edit_distance_solution.py

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    for i in range(m + 1):
        dp[i][0] = i     # delete all of word1[:i]
    for j in range(n + 1):
        dp[0][j] = j     # insert all of word2[:j]
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]          # characters already match
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],   # replace
                    dp[i - 1][j],       # delete from word1
                    dp[i][j - 1],       # insert into word1
                )
 
    return dp[m][n]
 
 
print(min_distance("horse", "ros"))              # 3
print(min_distance("intention", "execution"))    # 5

Recurrence: it’s LCS’s cousin — a matching character costs nothing and falls through to the diagonal; a mismatch pays 1 for whichever of replace/delete/insert leaves the cheapest remaining subproblem.

Complexity: Time $O(mn)$ , Space $O(mn)$ (rollable to $O(\min(m, n))$ ).

Recap

The state is almost always a prefix (or a pair of prefixes): dp[i]dp[i] for one sequence, dp[i][j]dp[i][j] for two.
Write the recurrence in one sentence before writing code — every solution above is short once that sentence is right.
1D problems (Climbing Stairs, House Robber, Coin Change, Word Break) look back a fixed or variable number of earlier states; 2D problems (LCS, Edit Distance, Unique Paths) compare a pair of prefixes cell by cell.
Most of these tables can be rolled down to $O(n)$ or $O(\min(m,n))$ space once the recurrence only reads the previous row.

Next: Hard Mix Problem Set — the finale of this track, mixing monotonic stacks, binary search, heaps, graphs, and linked lists in one final gauntlet.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Dynamic Programming Problem Set

How to use this set

1. Climbing Stairs — LC 70 — Easy

2. House Robber — LC 198 — Medium

3. Coin Change — LC 322 — Medium

4. Longest Increasing Subsequence — LC 300 — Medium

5. Longest Common Subsequence — LC 1143 — Medium

6. Unique Paths — LC 62 — Medium

7. Word Break — LC 139 — Medium

8. Edit Distance — LC 72 — Medium

Recap

Was this page helpful?