One Dimensional DP

Most “easy-to-medium” DP interview questions share one shape: the state is a single index i — usually “position in the array” or “position in the string” — and dp[i] answers “what’s the best result considering everything up to (or starting at) index i?” Once you can write that one sentence, the recurrence almost always falls out of it.

What you’ll learn

• Why the state for these problems is just dp[i] — one integer, no extra dimensions.
• Five classic 1D problems, each with its recurrence in math and a runnable solution: Climbing Stairs, House Robber, House Robber II, Coin Change (both variants), and Decode Ways.
• How circular constraints (House Robber II) reduce to two calls of the linear version.
• Space optimization: most of these only need the last one or two dp values, not the whole array.

The cue

You are looking at 1-D DP when…

• The input is a single sequence — an array or a string — and the answer at each position depends on one or two earlier positions, not on an arbitrary subset of them.
• The problem says “in how many ways”, “maximum/minimum total”, or “can you reach”, and a greedy choice provably fails because a local best can block a better global one (House Robber is the canonical example: taking the largest house first can cost you two neighbours).
• You can finish the sentence “dp[i] is the best answer considering the first i elements” — and the transition needs only dp[i-1], dp[i-2], or a fixed window back.
• Brute force is exponential in a suspiciously structured way: $2^n$ subsets or $2^n$ paths, where most branches recompute the same prefix.

The reframe: stop thinking about which elements to choose. Fix the last position and ask what choice you have there — take it or skip it, one step or two. Every 1-D DP is that question, and the recurrence is the answer written down.

Reach for something else when the state needs two indices (a second sequence, or a range — that is 2-D DP), when the state is a set rather than a position (bitmask DP), when the dependency reaches arbitrarily far back and needs a data structure to keep the best-so-far (monotonic deque, segment tree), or when a greedy actually is provably optimal — do not pay for a table you do not need.

The state: dp[i]

For every problem below, dp[i] means “the best answer considering arr[0..i]” — and the transition asks: given dp[i-1] and dp[i-2] (or similar), how do I get dp[i]? Write that sentence first, every time, before touching code.

Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways are there to reach step n? Reaching step i means your last hop was either 1 step from i - 1 or 2 steps from i - 2 — so the count at i is the sum of both.

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

climbing_stairs.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(5))    # expect 8
print(climb_stairs(10))   # expect 89

This is literally Fibonacci wearing a different costume — and it already uses the O(1) space trick: only the last two values are ever needed, so there’s no reason to keep a full array.

House Robber

Rob houses in a row for maximum total loot, but you can’t rob two adjacent houses. At house i, you either skip it (carry dp[i-1] forward) or rob it (take nums[i] plus the best from dp[i-2], since i-1 is now off-limits).

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

house_robber.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([2, 7, 9, 3, 1]))   # expect 12  (2 + 9 + 1)
print(rob([1, 2, 3, 1]))      # expect 4   (1 + 3)

House Robber II (circular street)

Now the houses form a circle — house 0 and house n - 1 are adjacent too. Robbing both the first and last house is never allowed together, so the answer is the better of two linear sub-problems: “rob houses 0..n-2” or “rob houses 1..n-1”. Reuse the exact function above, twice.

house_robber_ii.py

def rob_linear(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
    exclude_last = rob_linear(nums[:-1])    # never touch the last house
    exclude_first = rob_linear(nums[1:])    # never touch the first house
    return max(exclude_last, exclude_first)
 
 
print(rob_circular([2, 3, 2]))       # expect 3
print(rob_circular([1, 2, 3, 1]))    # expect 4

Circular constraints often reduce to two linear calls

Whenever “the first and last are adjacent” shows up, try solving the linear version twice — once excluding the first element, once excluding the last — and take the better result. It’s usually simpler than adding a whole new dimension to the state.

Coin Change: minimum coins

Given coin denominations and a target amount, find the fewest coins that sum to it (or report it’s impossible). Here the state is the amount itself: dp[a] is the minimum coins needed to make amount a. For each amount, try using one more of every coin and take the best.

$$dp[a] = 1 + \min_{c \,\in\, coins,\ c \le a} dp[a - c], \qquad dp[0] = 0$$

coin_change_min.py

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1
 
 
print(coin_change([1, 2, 5], 11))    # expect 3  (5 + 5 + 1)
print(coin_change([2], 3))           # expect -1 (impossible)

Coin Change II: count the ways

Same coins, same amount, but now count how many distinct combinations make that amount (order doesn’t matter — $\{1, 2\}$ and $\{2, 1\}$ are the same combination). The trick that stops double-counting: loop coins on the outside, amounts on the inside, so each coin is only ever “added” after the ones before it in the list have already been considered.

$$dp[a] \mathrel{+}= dp[a - c] \quad \text{for each coin } c,\ \text{processed one coin at a time}$$

coin_change_ii.py

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1                 # one way to make 0: use no coins
    for c in coins:            # coin on the OUTER loop avoids counting permutations twice
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]
 
 
print(change(5, [1, 2, 5]))   # expect 4  ({5}, {1,1,1,2}, {1,2,2}, {1,1,1,1,1})

Decode Ways

A digit string encodes letters ("1" -> A … "26" -> Z). Count the number of ways to decode it. dp[i] is the number of ways to decode the first i characters: it inherits dp[i-1] if the single digit at i-1 is valid (1-9), and also inherits dp[i-2] if the two-digit number ending at i-1 is valid (10-26).

$$dp[i] = \underbrace{dp[i-1] \cdot [\,s[i-1] \ne \text{'0'}\,]}_{\text{single digit}} +\ \underbrace{dp[i-2] \cdot [\,10 \le \text{int}(s[i-2:i]) \le 26\,]}_{\text{two digits}}$$

decode_ways.py

def num_decodings(s):
    if not s or s[0] == "0":
        return 0
    n = len(s)
    prev2, prev1 = 1, 1    # dp[0] = 1 (empty prefix), dp[1] = 1 (first char is valid)
    for i in range(2, n + 1):
        current = 0
        if s[i - 1] != "0":                       # single digit s[i-1] is valid (1-9)
            current += prev1
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:                  # two digits s[i-2:i] are valid (10-26)
            current += prev2
        prev2, prev1 = prev1, current
    return prev1
 
 
print(num_decodings("226"))   # expect 3  ("2,2,6" / "22,6" / "2,26")
print(num_decodings("06"))    # expect 0  (leading zero can't be decoded)

Filling the table, one index at a time

sketch 1D dp array filling left to right (Climbing Stairs) p5.js Pause Restart

dp[i] only ever needs dp[i-1] and dp[i-2] -- once those two are known, every later cell is O(1) to compute.

Space optimization: O(n) to O(1)

Look closely at every solution above — none of them ever read dp[i-3] or earlier. Whenever the transition only reaches back a fixed number of steps (1 or 2, here), you don’t need the whole array: keep just the last one or two values in plain variables and slide them forward each iteration, exactly like prev2, prev1 = prev1, prev1 + prev2 above. That’s an O(n) space table shrunk to O(1) with no change in time complexity.

Dry run

House Robber — nums = [2, 7, 9, 3, 1]. Two rolling variables: prev1 is dp[i-1] (best through the previous house) and prev2 is dp[i-2].

i	num	skip = prev1	rob = prev2 + num	dp[i]	prev2, prev1 after
0	2	0	0 + 2 = 2	2	0, 2
1	7	2	0 + 7 = 7	7	2, 7
2	9	7	2 + 9 = 11	11	7, 11
3	3	11	7 + 3 = 10	11	11, 11
4	1	11	11 + 1 = 12	12	11, 12

Answer 12, from 2 + 9 + 1.

Four things this makes visible:

• Step 3 is where greedy dies. House 3 is worth 3, and skipping it wins — dp[3] stays 11. A greedy “rob it if you can” would take 3 (total 14 so far by its own count) and then be forbidden from house 4. The DP compares both futures instead of guessing.
• The answer is not “every other house”. 2 + 9 + 1 skips two in a row between 9 and 1… which it must, because 3 sits between them. Patterns like “alternate houses” or “sum the odd indices” fail on this exact input, which is why it is LeetCode’s example.
• prev2 lags one step behind on purpose. At i = 3, prev2 is dp[1] = 7, not dp[2]. The single most common bug here is updating prev1 before reading it for prev2 — Python’s tuple assignment prev2, prev1 = prev1, max(...) evaluates the whole right-hand side first, which is what makes the one-liner safe. Writing it as two statements requires a temporary.
• Both variables start at 0, and that is dp[-1] and dp[-2]. The loop needs no special case for i = 0 or i = 1, because “best loot from no houses” is genuinely 0. Compare Climbing Stairs, where the bases are 1, 1 — an empty staircase has one way to be climbed (do nothing), not zero.

Climbing Stairs — n = 5: the dp sequence is 1, 1, 2, 3, 5, 8, so the answer is 8. It is Fibonacci offset by one, and the offset is the whole difficulty: dp[0] = 1 because there is exactly one way to stand still. Setting dp[0] = 0 yields 0, 1, 1, 2, 3, 5 — every answer shifted, and every small test still “looking plausible”.

Complexity

Problem	Time	Space (naive)	Space (rolling)
Climbing Stairs	$O(n)$	$O(n)$	$O(1)$ — two variables
House Robber	$O(n)$	$O(n)$	$O(1)$
House Robber II (circular)	$O(n)$	$O(n)$	$O(1)$ — two passes
Coin Change, min coins	$O(n \cdot A)$	$O(A)$	$O(A)$ — the array is the state
Coin Change II, count ways	$O(n \cdot A)$	$O(A)$	$O(A)$
Decode Ways	$O(n)$	$O(n)$	$O(1)$
Word Break	$O(n^2 \cdot L)$	$O(n)$	$O(n)$

The rolling-variable trick applies whenever the recurrence reaches back a fixed number of positions: keep that many variables and drop the array. It does not apply to Coin Change, where dp[a] depends on dp[a - c] for arbitrary coin values — there is no fixed window, so the whole array must stay live.

The complexity claim interviewers actually probe

Naming $O(n)$ is easy. The follow-up is “and the space?” — the answer they want is ”$O(n)$ as written, $O(1)$ with two rolling variables, because the recurrence only reaches back two positions.” Then the sharper one: “can you still recover which houses you robbed?” No — the rolling form has discarded that. You would keep the array and walk it backwards, comparing dp[i] with dp[i-1] to see whether house i was taken. Space optimisation costs you the decision history, and saying so unprompted is the whole point.

The variant map

Problem	dp[i] means	Transition	The catch
LC 70 Climbing Stairs	ways to reach step i	dp[i-1] + dp[i-2]	bases are 1, 1, not 0, 1
LC 746 Min Cost Climbing Stairs	min cost to stand on i	cost[i] + min(dp[i-1], dp[i-2])	you may start at step 0 or 1
LC 198 House Robber	best loot through i	max(dp[i-1], dp[i-2] + nums[i])	one-element and two-element arrays
LC 213 House Robber II	—	run LC 198 twice	nums[:-1] and nums[1:]; single house must be special-cased
LC 337 House Robber III	best loot in this subtree	(rob, skip) pair returned upward	it is a tree, so this becomes tree DP
LC 91 Decode Ways	decodings of the first i chars	dp[i-1] if 1-digit valid, + dp[i-2] if 2-digit in 10..26	'0' is never a valid single digit; '06' is not 6
LC 322 Coin Change	fewest coins for amount i	min(dp[i - c] + 1) over coins	inf sentinel, and the answer is -1 when it survives
LC 518 Coin Change II	ways to make amount i	dp[i] += dp[i - c]	loop nesting decides combinations vs permutations — see knapsack
LC 139 Word Break	is the prefix of length i splittable	any(dp[j] and s[j:i] in words)	put the dictionary in a set
LC 55/45 Jump Game	reachability / min jumps	greedy beats DP here	greedy reachability is $O(n)$ with $O(1)$ space
LC 152 Max Product Subarray	best product ending at i	track max and min	a negative flips them, so one variable is not enough
LC 300 LIS	longest increasing subseq. ending at i	max(dp[j]) + 1 for j < i, nums[j] < nums[i]	$O(n^2)$; patience sorting gets $O(n \log n)$

Pitfalls

• Off-by-one in the base case. Climbing Stairs needs dp[0] = 1 (“one way to stand still”); House Robber needs dp[-1] = dp[-2] = 0. Getting this wrong shifts every value and still produces plausible numbers on small inputs.
• Updating prev1 before reading it as prev2. Use the tuple assignment prev2, prev1 = prev1, max(prev1, prev2 + num), which evaluates the right side first. As two separate statements it needs an explicit temporary.
• Rolling the array away when you need the choices back. $O(1)$ space discards the decision history. Keep the array if the follow-up asks which elements were used.
• inf leaking into the answer in Coin Change. If dp[amount] is still inf, return -1 — do not return inf, and do not let it be added to (inf + 1 silently propagates a wrong “answer” into later cells if you skip the reachability check).
• Forgetting that '0' decodes to nothing in LC 91. s[i] != '0' gates the one-digit branch, and the two-digit branch needs 10 <= int(s[i-1:i+1]) <= 26 — which excludes '06' as well as '27'.
• Assuming a greedy works. House Robber’s [2,7,9,3,1] and Max Product’s negatives are the two standard counterexamples. Conversely, Jump Game’s greedy is optimal — so the claim has to be checked, not assumed either way.
• Single- and two-element inputs. Most of these problems allow n = 1, and House Robber II additionally needs n == 1 special-cased, because nums[:-1] and nums[1:] are both empty.
• Reaching for 2-D too early. If the recurrence only looks back a fixed number of positions, one dimension is enough. A second index should be forced by a second sequence or a range, not added out of caution.

Interview follow-ups

They ask	What they’re checking	The answer
“Why not greedy?”	Whether you can justify the DP	Because a locally best choice can forfeit a strictly better future — in [2,7,9,3,1], robbing house 3 blocks house 4 and loses. The DP compares both futures instead of committing
“Can you do it in O(1) space?”	The standard optimisation	Yes when the recurrence reaches back a fixed number of positions: keep that many rolling variables. Coin Change cannot, because dp[a-c] reaches back by arbitrary coin values
“Now tell me which houses you robbed”	The cost of that optimisation	The rolling form has discarded it. Keep the array and walk backwards: if dp[i] != dp[i-1], house i was taken. That is $O(n)$ space back
“Recursive with memoisation instead?”	Whether you see them as the same	Same complexity, top-down instead of bottom-up. @lru_cache on f(i) is often quicker to write and skips unreachable states; the iterative version has no recursion limit and better constants
“Houses are in a circle”	Composition	Run the linear solution twice — excluding the last house, then the first — and take the max, since house 0 and house n−1 cannot both be robbed. Special-case a single house
“Houses form a tree”	Generalisation	Each node returns a (rob_me, skip_me) pair; a parent that robs must skip both children. Same idea, post-order instead of left-to-right
“What if the array is 10^7 long?”	Practicality	$O(n)$ time is fine; the $O(1)$-space form matters because a $10^7$ Python list of ints is roughly 400 MB. Rolling variables make it free
“Coin Change returns inf”	Sentinel discipline	That means the amount is unreachable, so return -1. Guard before adding, or the sentinel propagates into later cells and yields a wrong number rather than an obvious failure

Practice — real LeetCode problems

House Robber is the canonical “take it or skip it” one-dimensional DP, and it is asked constantly. Do all three in order: the second adds a circular constraint you handle by running the first one twice, and the third replaces the numeric choice with a choice over a dictionary.

LC 198 — House Robber · Medium

Problem. Each house on a street holds nums[i] in cash, but robbing two adjacent houses triggers the alarm. Return the maximum you can take.

Constraints. 1 <= len(nums) <= 100, 0 <= nums[i] <= 400.

Examples. [1,2,3,1] gives 4 (houses 0 and 2) · [2,7,9,3,1] gives 12 (houses 0, 2 and 4)

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The state is “the best I can do considering the first i houses”, split by whether house i was robbed. Splitting on the last decision is the same move that derived Climbing Stairs; here the decision carries a value.

Time $O(n)$. Space $O(1)$.

The textbook single-array form is dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip house i and keep dp[i-1], or rob it and add dp[i-2]. The two-variable version is that with the table thrown away.

• Greedy fails. Taking the largest remaining house and discarding its neighbours is wrong on [3,4,3]: the greedy grabs the 4, which blocks both 3s, for a total of 4 — the answer is 6. Have that counterexample ready; interviewers ask why a local choice is not enough.
• [2,1,1,2] = 4 is the discriminating case for the tuple update. If you assign take and then compute skip from the new take, you allow adjacent houses and get 6.
• Single house must return nums[0], and the loop handles it because both accumulators start at 0.
• All zeros returns 0, and no house is ever forced.

Follow-ups you should expect: “Which houses?” — keep a parent array or rerun the decision backwards. “Circular street?” — LC 213, next. “A binary tree instead of a street?” — LC 337, in the Tree DP page. “No two houses within k?” — the recurrence becomes max(dp[i-1], dp[i-k-1] + nums[i]). “Must rob exactly k houses?” — add k as a second dimension.

LC 213 — House Robber II · Medium

Problem. Same rule, but the houses form a circle — the first and last are adjacent. Return the maximum.

Constraints. 1 <= len(nums) <= 100, 0 <= nums[i] <= 1000.

Examples. [2,3,2] gives 3 (you cannot take both 2s now) · [1,2,3,1] gives 4

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

You cannot fix a circular dependency inside one left-to-right pass, because the decision at index 0 constrains index n-1, which you have not reached yet. The standard escape is to enumerate the thing that closes the loop — here, whether house 0 is robbed — and solve a linear problem for each case.

Note the two runs are not “exclude first” and “exclude last” as an exhaustive partition of plans; they overlap, and that is fine. What matters is that every valid circular plan is feasible in at least one run, and every plan feasible in a run is valid on the circle.

Time $O(n)$, two passes. Space $O(1)$.

• Length 1 must be special-cased. nums[:-1] and nums[1:] are both empty, so the helper returns 0 and you would answer 0 instead of nums[0].
• Length 2 works without a special case: one slice holds each house, and the answer is the max. Worth checking, because many solutions guard len < 3 unnecessarily.
• [2,3,2] = 3 is the case that separates this from LC 198. If you get 4 you are still solving the linear version.

Follow-ups you should expect: “Why exactly two runs?” — because there is one adjacency to break and two ways to break it. “Circular maximum subarray sum (LC 918)?” — same trick: either the answer is a normal Kadane result, or it wraps, which means the complement is a minimum subarray. “Robber on a cycle of length 1?” — the special case above. “Robber on a general graph?” — that is maximum weight independent set, NP-hard; trees and cycles are the tractable cases.

LC 139 — Word Break · Medium

Problem. Given a string s and a dictionary wordDict, decide whether s can be segmented into a sequence of one or more dictionary words. Words may be reused.

Constraints. 1 <= len(s) <= 300, 1 <= len(wordDict) <= 1000, words are distinct, lowercase letters only.

Examples. s = "leetcode", wordDict = ["leet","code"] gives True · s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] gives False

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

One-dimensional DP over prefixes of a string rather than over an array of numbers. dp[i] answers a yes/no question about s[:i], and the transition asks where the last word started.

Time $O(n^2 \cdot L)$ where $L$ is the average word length — $n^2$ split points, and each slice-and-hash costs $O(L)$. Space $O(n)$ plus the set.

• dp[0] = True is the base case. Without it nothing is ever reachable and everything returns False.
• Greedy longest-match fails. On "catsandog" with ["cats","dog","sand", "and","cat"], taking "cats" first leaves "andog", which dead-ends. The DP also tries "cat" + "sand" — and that dead-ends too, which is why the answer is False. This single case kills both the greedy and any solution that returns early on the first failed branch.
• Reuse is allowed, so "applepenapple" is fine with two "apple"s. Nothing in the recurrence forbids it — which is exactly why an unbounded-style DP is the right model.
• The break is correctness-neutral but a real speedup: you only need one valid split.

Two useful refinements. Bound the inner loop by the longest dictionary word instead of scanning to 0. Or replace the set with a trie and walk forward from each dp[j] that is True, which avoids building substrings at all — the answer to “what if the dictionary is enormous?”

Follow-ups you should expect: “Return one valid segmentation?” — store the split point that worked and walk back. “Return all segmentations (LC 140)?” — exponentially many, so memoized backtracking, not a boolean table. “Count the segmentations?” — replace the boolean with a sum; the loop stops breaking early. “Why not BFS over indices?” — that works and is the same graph, with dp as the visited set.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

9 problems

1 easy8 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.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○70Climbing StairseasyThe exact template aboveNeetCode 150Blind 75LeetCode Top Interview 150
• ○139Word Breakmedium`dp[i]` = "can the first `i` characters be segmented into dictionary words?", checking every valid split pointNeetCode 150Blind 75LeetCode Top Interview 150googleamazonmetabytedance
• ○300Longest Increasing SubsequencemediumNeetCode 150Blind 75LeetCode Top Interview 150googlemicrosoftbytedanceuber
• ○322Coin ChangemediumMinimum coins to reach an amountNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemicrosoftbytedance
• ○91Decode WaysmediumA 1-or-2-step lookback on a digit stringNeetCode 150Blind 75
• ○198House RobbermediumLinear adjacency constraintNeetCode 150Blind 75LeetCode Top Interview 150
• ○213House Robber IImediumCircular version, solved as two linear callsNeetCode 150Blind 75
• ○518Coin Change IImediumCount the distinct combinations insteadNeetCode 150
• ○1824Minimum Sideway Jumpsmedium

Self-check

pch.quizTag One-dimensional DP — self-check

1. On `nums = [2, 7, 9, 3, 1]`, why does House Robber skip house 3 (value 3)?

   A Because 3 is the smallest value B Because dp[3] = max(skip = 11, rob = dp[1] + 3 = 10) — taking it would forfeit house 4, and the DP compares both futures rather than committing C Because you must alternate houses D Because 9 was already taken
   pch.quizShowAnswer

   B — Because dp[3] = max(skip = 11, rob = dp[1] + 3 = 10) — taking it would forfeit house 4, and the DP compares both futures rather than committing — The answer is 2 + 9 + 1 = 12, which skips two houses in a row. Any 'take every other house' heuristic fails on this exact input, which is why it is the problem's example.

2. Climbing Stairs has bases `dp[0] = dp[1] = 1`. Why is dp[0] one rather than zero?

   A Convention B Because there is exactly one way to climb an empty staircase — do nothing. Setting it to 0 shifts every subsequent value while still looking plausible on small inputs C Because you always start on step 1 D Because the recurrence needs a non-zero seed
   pch.quizShowAnswer

   B — Because there is exactly one way to climb an empty staircase — do nothing. Setting it to 0 shifts every subsequent value while still looking plausible on small inputs — Contrast House Robber, where the same slots are genuinely 0 — 'best loot from no houses'. The base case follows from what dp[i] MEANS, which is why writing that sentence first is the actual technique.

3. Why is `prev2, prev1 = prev1, max(prev1, prev2 + num)` safe as a one-liner?

   A Because Python caches the old values B Because tuple assignment evaluates the entire right-hand side before binding either name, so `max` still sees the old prev1 and prev2 C Because max() copies its arguments D It is not safe; it needs a temporary
   pch.quizShowAnswer

   B — Because tuple assignment evaluates the entire right-hand side before binding either name, so `max` still sees the old prev1 and prev2 — Written as two separate statements, updating prev1 first destroys the value prev2 needs — a genuine bug that yields answers slightly too large. The tuple form is what makes the trick idiomatic in Python.

4. Which of these problems CANNOT be reduced to O(1) space?

   A House Robber B Coin Change — dp[a] depends on dp[a - c] for arbitrary coin values, so there is no fixed window to keep and the whole array must stay live C Climbing Stairs D Decode Ways
   pch.quizShowAnswer

   B — Coin Change — dp[a] depends on dp[a - c] for arbitrary coin values, so there is no fixed window to keep and the whole array must stay live — The rolling trick works exactly when the recurrence reaches back a fixed number of positions. That is the test to apply, rather than assuming every 1-D DP compresses.

5. You optimised House Robber to two variables. The interviewer asks which houses you robbed. What do you say?

   A Recompute greedily from the answer B That the rolling form discarded the decision history — keep the array and walk backwards, taking house i whenever dp[i] != dp[i-1], at O(n) space C Store the answer in a set as you go D It is impossible to recover
   pch.quizShowAnswer

   B — That the rolling form discarded the decision history — keep the array and walk backwards, taking house i whenever dp[i] != dp[i-1], at O(n) space — Naming the trade-off before being pushed on it is the point: space optimisation is not free, it costs you the ability to reconstruct the choice.

6. House Robber II puts the houses in a circle. What changes?

   A Add a modulo to the indices B Run the linear solution twice — once on nums[:-1], once on nums[1:] — and take the max, since house 0 and house n−1 cannot both be robbed. Special-case a single house C Rob every other house around the circle D Use 2-D DP with a 'took first house' flag
   pch.quizShowAnswer

   B — Run the linear solution twice — once on nums[:-1], once on nums[1:] — and take the max, since house 0 and house n−1 cannot both be robbed. Special-case a single house — The two-flag 2-D version also works but is more code for the same result. The single-house case is the edge case that breaks the two-pass version, since both slices are then empty.

Recall card

• Cue — one sequence, and the answer at i depends on a fixed number of earlier positions. Counting, max/min total, or reachability where greedy provably fails.
• First move — write the sentence “dp[i] is … considering the first i elements”, then ask what choice exists at i. The recurrence is that sentence.
• Climbing Stairs — dp[i] = dp[i-1] + dp[i-2], bases 1, 1.
• House Robber — dp[i] = max(dp[i-1], dp[i-2] + nums[i]), bases 0, 0.
• Base cases come from the meaning, not from convention — that is why the two above differ.
• $O(1)$ space whenever the reach-back is fixed: prev2, prev1 = prev1, max(...), one tuple assignment. Not possible for Coin Change.
• Rolling away the array discards the choices — keep it if asked which elements were used.
• Circular → run it twice on nums[:-1] and nums[1:]. Tree → return a (take, skip) pair upward.

Recap

• The state for these problems is one index: dp[i] means “the best answer using/considering everything up through position i.”
• Climbing Stairs and House Robber both look back exactly 2 positions — the same shape as Fibonacci with a different combine step.
• House Robber II’s circular constraint reduces to two linear calls, each excluding one endpoint.
• Coin Change minimizes over choices (min + 1 per coin); Coin Change II counts combinations by looping coins on the outside to avoid counting the same set in a different order.
• Decode Ways looks back 1 or 2 positions depending on whether the single digit or the two-digit pair is a valid letter code.
• Whenever the lookback is a fixed, small number of steps, drop the full dp array for O(1) space — just carry the last few values forward.

Next: Two Dimensional DP and Knapsack — states with two indices, starting with the 0/1 knapsack and its rolling-array space optimization.