Dynamic Programming Problem Set

Dynamic programming problems are won or lost on one sentence: what does dp[i] (or 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 and a pass — 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 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 n steps. Each move you can climb either 1 or 2 steps. Return the number of distinct ways to reach the top.

1 <= 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

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

Recurrence: reaching step i means your last hop was 1 step from i - 1 or 2 steps from i - 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 nums representing loot in houses arranged in a row, return the maximum amount you can rob without robbing two adjacent houses.

1 <= len(nums) <= 100
0 <= 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

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)

Recurrence: skipping house i carries forward dp[i-1]; robbing it adds nums[i] to dp[i-2] (since i-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 coins and a target amount, return the fewest coins needed to make up amount. Each coin can be used an unlimited number of times. Return -1 if it’s impossible.

1 <= len(coins) <= 12
0 <= 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

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)

Recurrence: dp[i] looks back at every coin c that fits and takes the cheapest way to reach i - 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 nums, return the length of the longest strictly increasing subsequence (not necessarily contiguous).

1 <= 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

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])

Recurrence: every earlier index j with a smaller value is a valid predecessor — dp[i] takes the best one and adds itself. The answer is 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_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 text1 and text2, return the length of their longest common subsequence, or 0 if none exists.

1 <= 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

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)

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] 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 n grid and can only move down or right. Return the number of distinct paths to the bottom-right corner.

1 <= 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

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

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] 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 s and a dictionary of strings word_dict, return True if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.

1 <= 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

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)

Recurrence: dp[i] asks “is there some earlier breakable prefix j such that the piece from j to i is a dictionary word?” — exactly one True 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 word1 and word2, return the minimum number of single-character insert, delete, or replace operations to convert word1 into word2.

0 <= 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

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

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))$ ).

Complexity

Read a DP bound as states x transitions. Almost every entry below is a 1D or 2D table with a constant or linear transition, and the space column is where the follow-up lives.

#	Problem	States	Transition	Time	Space (naive -> rolled)
1	Climbing Stairs	$n$	$O(1)$	$O(n)$	$O(n)$ -> $O(1)$ (two variables)
2	House Robber	$n$	$O(1)$	$O(n)$	$O(n)$ -> $O(1)$
3	Coin Change	$n \times$ amount	$O(\text{coins})$	$O(\text{amount} \times C)$	$O(\text{amount})$
4	Longest Increasing Subsequence	$n$	$O(n)$	$O(n^2)$ , or $O(n \log n)$ with patience/bisect	$O(n)$
5	Longest Common Subsequence	$n \times m$	$O(1)$	$O(nm)$	$O(nm)$ -> $O(\min(n,m))$ (two rows)
6	Unique Paths	$m \times n$	$O(1)$	$O(mn)$	$O(mn)$ -> $O(n)$ (one row); or $O(1)$ via a binomial coefficient
7	Word Break	$n$	$O(n)$ substring checks	$O(n^2)$ (plus substring cost)	$O(n)$
8	Edit Distance	$n \times m$	$O(1)$	$O(nm)$	$O(nm)$ -> $O(\min(n,m))$

Four things to get right:

Coin Change is $O(\text{amount} \times C)$ , which is pseudo-polynomial. It is polynomial in the value of amount, not in the input length — the same class as knapsack’s $O(nW)$ . Calling it polynomial is the standard imprecision.
LIS has two well-known bounds and they are different algorithms. The $O(n^2)$ table DP is what most people write; the $O(n \log n)$ version maintains a tails array and binary-searches it. The tails array is not a valid LIS — only its length is meaningful.
Rolling a 2D table to 1D is nearly always available, because a row usually depends only on the previous row. Do it along the shorter dimension: $O(\min(n,m))$ , not $O(n)$ .
Unique Paths has a closed form. It is $\binom{m+n-2}{m-1}$ — $O(\min(m,n))$ time and $O(1)$ space with no table at all. Worth offering after the DP, because it shows you noticed the problem is counting lattice paths.

Pitfalls

Coin Change: using -1 as the unreachable sentinel inside the table. -1 compares as less than every real count, so min picks it and the answer propagates garbage. Use float("inf") (or amount + 1) internally and convert to -1 only at the return.
Coin Change: dp[0] = 0 versus dp[0] = 1. Zero coins make zero. Setting it to 1 shifts every answer. And coin_change([1], 0) must return 0, not -1 — verified.
Coin Change vs Coin Change II: the loop order is the whole difference. Coin outside, amount inside counts combinations; amount outside, coin inside counts permutations. For coins=[1,2,5], amount=5 that is 4 against 9 — verified. Both loops look equally reasonable and only one answers the question asked.
House Robber: initialising from nums[0] without handling a one-element array. nums[1:] is empty and safe in Python, but an explicit if len(nums) == 1 is clearer than relying on it.
LIS: bisect_right instead of bisect_left. bisect_left gives the strictly increasing length; bisect_right gives longest non-decreasing. On [2,2,2] that is 1 against 3 — verified. LC 300 wants strict, so bisect_left.
LIS: returning the tails array as the subsequence. Its length is correct; its contents are generally not an actual increasing subsequence of the input. Reconstructing the real one needs a parent-pointer pass.
LCS / Edit Distance: getting the table dimensions off by one. The table is (n+1) x (m+1), with row 0 and column 0 as the empty-prefix base cases. Sizing it n x m forces awkward special cases everywhere.
Edit Distance: forgetting that the diagonal is free on a match. On a[i] == b[j] the cost is dp[i-1][j-1] with no +1. Adding 1 unconditionally turns it into a different (and wrong) metric.
Word Break: greedy longest-match-first. It fails on the classic "aaaaaab" shape where a long early match strands the tail. DP over prefixes, or memoised recursion — not greedy.
Word Break: not converting wordDict to a set. in on a list is $O(k)$ per check, turning the whole thing quadratic in the dictionary size for no reason.
Rolling a 2D table in the wrong direction. When you collapse to one row, the iteration direction decides whether you read the previous row or the partially-updated current one. 0/1 knapsack must iterate the capacity descending; unbounded coin change iterates ascending. Same code, different meaning.
Unique Paths: initialising the first row and column to 0. They are 1 — there is exactly one path along an edge.

Drills

Three micro-drills on the lines that decide these problems.

Drill 1 — the unreachable sentinel

Drill 2 — loop order decides combinations or permutations

Drill 3 — LIS in O(n log n), and the bisect side

Interview follow-ups

They ask	On which problem	The answer
“Reduce the space”	Climbing Stairs, House Robber	Each state depends only on the previous one or two, so keep two variables: $O(1)$ . This is the first follow-up on almost every 1D DP
“Reduce the space on a 2D table”	LCS, Edit Distance	A row depends only on the row above, so keep two rows — and roll along the shorter dimension for $O(\min(n,m))$ . You lose the ability to reconstruct the path, which is the trade to name
“Now return the actual subsequence, not its length”	LCS, LIS	You need the full table (or parent pointers) to walk back, so the rolled version no longer works. For LIS specifically, the `tails` array’s contents are not a real subsequence — reconstruction needs a separate parent array
“What is the complexity of Coin Change, precisely?”	Coin Change	$O(\text{amount} \times C)$ , and it is pseudo-polynomial — polynomial in the value of `amount`, not in the input’s length. Same class as knapsack’s $O(nW)$
“Count the ways instead of the minimum”	Coin Change	LC 518, and the loop order changes: coin outside for combinations. `coins=[1,2,5], amount=5` gives 4 combinations but 9 permutations — same recurrence, different question
“Why does the loop order matter at all?”	Coin Change II	With the coin outside, each coin’s contribution is folded in once, so a multiset is counted once regardless of order. With the amount outside, every coin gets a chance at every amount, so orderings are counted separately
“Do LIS faster than $O(n^2)$ ”	LIS	$O(n \log n)$ with a `tails` array and `bisect_left`. `tails[i]` is the smallest possible tail of an increasing subsequence of length `i+1`, and its length is the answer
“Non-decreasing instead of strictly increasing?”	LIS	Switch to `bisect_right`. On `[2,2,2]` that is 3 instead of 1 — one function name, a different problem
“Is there a closed form?”	Unique Paths	Yes — $\binom{m+n-2}{m-1}$ , since every path is a fixed multiset of right and down moves. $O(\min(m,n))$ time, $O(1)$ space, no table
“Why not solve Word Break greedily?”	Word Break	A long early match can strand the tail, so greedy fails on the `"aaaaaab"` shape. DP over prefixes, or memoised recursion. Also convert `wordDict` to a set — list membership makes it needlessly quadratic
“Add a cost per operation”	Edit Distance	The recurrence structure is unchanged; each branch takes its own weight instead of `+1`. Only the match case stays free, at `dp[i-1][j-1]`
“What if you can also transpose adjacent characters?”	Edit Distance	Damerau-Levenshtein — one extra branch reading `dp[i-2][j-2]` when the two characters are swapped. Naming it is enough

Practice

Every problem on this page, generated from the problem database — so each row carries its sheet membership and reported companies, and the checkboxes remember what you have finished. The walkthroughs above are the teaching; this is the tracker.

7 problems

1 easy6 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

70Climbing StairseasyNeetCode 150Blind 75LeetCode Top Interview 150
72Edit DistancemediumNeetCode 150LeetCode Top Interview 150googleamazonmicrosoftbytedance
139Word BreakmediumNeetCode 150Blind 75LeetCode Top Interview 150googleamazonmetabytedance
322Coin ChangemediumNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemicrosoftbytedance
1143Longest Common SubsequencemediumNeetCode 150googleamazonmicrosoft
62Unique PathsmediumNeetCode 150Blind 75
198House RobbermediumNeetCode 150Blind 75LeetCode Top Interview 150

Self-check

pch.quizTag pch.quizDefaultTitle

In Coin Change, why use float("inf") rather than -1 as the in-table sentinel for "unreachable"?

pch.quizShowAnswer

B — -1 compares as smaller than any real count, so `min` selects it and the garbage propagates through the table — The recurrence takes a minimum, so the sentinel must lose every comparison -- infinity does, -1 wins them all. Verified: coin_change([2], 3) returns -1 with an infinity sentinel and produces nonsense with a -1 sentinel. Convert to -1 at the return, not inside the table. (amount + 1 also works, since no answer can exceed it.)
What should `coin_change([1], 0)` return?

pch.quizShowAnswer

B — 0 -- zero coins is a valid way to make zero, so dp[0] = 0 — dp[0] = 0 is the base case the whole table is built from, and it is also the correct answer for amount 0. Setting dp[0] = 1 shifts every subsequent answer by one, and returning -1 here treats an achievable amount as impossible. Verified as part of the drill's expected output [3, -1, 0, 1].
For coins [1, 2, 5] and amount 5, counting the ways gives 4 with one loop order and 9 with the other. Which is which?

pch.quizShowAnswer

B — Coin outside gives 4 (combinations); amount outside gives 9 (permutations) — With the coin outside, each coin's contribution is folded in exactly once, so a multiset is counted once whatever the order. With the amount outside, every coin gets a shot at every amount, so 1+2+2 and 2+1+2 count separately. Verified 4 against 9. LC 518 wants combinations -- and both loops look equally natural, which is why swapping them silently answers the wrong question.
LIS with `bisect_right` instead of `bisect_left`. What changes?

pch.quizShowAnswer

B — bisect_right computes the longest NON-DECREASING subsequence: [2,2,2] gives 3 instead of 1 — bisect_left places an equal value on top of the existing one, so equal values cannot extend the subsequence -- strict. bisect_right places it after, so they can. Verified: [2,2,2] gives 1 versus 3, and [7,7,7,7] gives 1 versus 4, while both give 4 on [10,9,2,5,3,7,101,18]. LC 300 wants strict.
The O(n log n) LIS returns len(tails). Is `tails` itself a longest increasing subsequence?

pch.quizShowAnswer

B — No -- only its length is meaningful; its contents are generally not a subsequence of the input at all — tails[i] is the smallest possible tail of *some* increasing subsequence of length i+1, and those tails can come from different, incompatible subsequences. The array is a bookkeeping device. If the problem wants the actual subsequence you need parent pointers recorded as you go -- a common follow-up, and a genuinely different amount of work.
Collapsing a 2D DP table to a single row: what does the iteration direction control?

pch.quizShowAnswer

B — Whether you read the previous row or the partially-updated current one -- 0/1 knapsack needs descending capacity, unbounded coin change needs ascending — Once there is one row, cells you already updated in this pass represent the *current* row while untouched cells still hold the previous one. Descending capacity guarantees you read the old value, so each item is used at most once (0/1). Ascending deliberately reads the new value, so an item can be reused (unbounded). Same three lines, opposite semantics.
Why is Coin Change described as pseudo-polynomial?

pch.quizShowAnswer

B — Its bound O(amount x C) is polynomial in the *value* of amount, not in the input's length -- the same class as knapsack's O(nW) — An amount of 10^9 is ten characters of input but a billion table entries. That is why the constraints on LC 322 cap the amount at 10^4 rather than letting it be arbitrary. Calling the bound simply "polynomial" is the standard imprecision, and it matters as soon as someone asks what happens when the amount grows.
Unique Paths has a closed form. What is it, and why is that worth mentioning?

pch.quizShowAnswer

B — C(m+n-2, m-1) -- every path is a fixed multiset of right and down moves, giving O(min(m,n)) time and O(1) space with no table — Any path takes exactly m-1 downs and n-1 rights in some order, so counting paths is counting arrangements of those moves. Offering it after the DP shows you recognised the problem is counting lattice paths rather than just filling a grid -- and it is a genuine improvement, from O(mn) to O(min(m,n)).

Recap

The state is almost always a prefix (or a pair of prefixes): dp[i] for one sequence, 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.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading