On this page

1D DP & Classic Sequences

You are walking along a row of houses, a row of stairs, a string of digits, or a list of daily stock prices. At every position you make a small decision: take this house or skip it, step one stair or two, read this digit alone or glue it to the one before, buy today or wait. The best (or the number of) ways to finish depends on the decision you make now and on nothing else from your past except one or two numbers.

That is 1D dynamic programming: the table is a single row indexed by position, dp[i] is "the answer for the first i items" (or "for a choice ending at i"), and each entry reads a constant number of entries just before it. Because it only ever looks a step or two back, the whole table usually collapses into two or three variables that roll forward. The result is an -time, -space algorithm that fits in ten lines — and that a surprising number of interview and production problems reduce to.

This lesson assumes DP Foundations (state, transition, base case, memoization vs tabulation) and Recursion & Induction. It is the first "problem family" lesson of the DP module; The Knapsack Family comes next and adds a second dimension (capacity).

Why this exists

Many problems have a natural left-to-right order: time (days of prices), space (houses on a street), or text (characters of a string). If the decision at position only interacts with a bounded number of earlier positions, the problem is a 1D DP. Recognising this turns exponential "try every subset of days" searches into a single linear pass.

Some history, because these problems did not start as interview puzzles:

  • Fibonacci numbers (Leonardo of Pisa, Liber Abaci, 1202) are the original 1D recurrence: . Counting the ways to climb stairs one or two at a time gives exactly these numbers, and the same "count by the last move" argument goes back to Indian prosody (Pingala and later Hemachandra counted rhythms built from short and long syllables).
  • Maximum subarray was posed by Ulf Grenander in 1977 for pattern detection in digitised images. Jay Kadane found the linear-time algorithm in about a minute during a seminar at Carnegie Mellon; Jon Bentley popularised the story in Programming Pearls (column 8, "Algorithm Design Techniques", 1984).
  • The Viterbi algorithm (Andrew Viterbi, 1967), which decodes convolutional codes in every mobile phone and finds the most likely hidden states in speech recognisers, is a 1D DP over time where each time step holds a small vector of states. The stock-trading problems below are a toy version of exactly that: a 1D DP with a few states per day.

Pattern triggers

If the problem says or has…Think of…
"how many ways to reach step " with a few allowed step sizesCounting by last move: dp[i] = dp[i-1] + dp[i-2] (+ …) (Fibonacci-style)
"minimum cost to reach the top", each step costs somethingMin over the last move: dp[i] = min(dp[i-1] + c, dp[i-2] + c')
"cannot take two adjacent items" (houses, seats, days)House robber: dp[i] = max(dp[i-1], dp[i-2] + a[i])
Same, but the items are in a circleTwo linear runs: drop the first item, or drop the last
Same, but the items form a treeTree DP: each node returns (best if taken, best if skipped)
"taking value deletes all and "Bucket by value, then house robber on the buckets (delete-and-earn)
"number of ways to split / decode a string" where pieces have length 1 or 2Decode ways: dp[i] = [valid 1-char]·dp[i-1] + [valid 2-char]·dp[i-2]
"largest sum of a contiguous subarray"Kadane: best sum ending here = max(a[i], prev + a[i])
"largest product of a contiguous subarray"Track both max and min ending here (a negative flips them)
"can you reach the end" with jump lengthsDP over reachability, or the greedy "furthest reach"
"buy and sell" with rules (one transaction, many, cooldown, fee, at most )State-machine DP: a few states per day (holding / not holding / cooling down)
Answer at needs only , Rolling variables: space
up to with a linear recurrenceMatrix Exponentiation

The meta-trigger: you can process the input in one direction, and the "memory" you need about the past is a small, fixed number of values. If the memory you need grows (a set of chosen items, a remaining capacity), you need another dimension — that is Knapsack and beyond.

Intuition & first principles

Counting by the last move

You stand on stair 5. You can climb 1 or 2 stairs per move. How many different move sequences got you here?

Ask: what was your last move? Either a 1-step from stair 4, or a 2-step from stair 3. No other option. Every sequence ending with "1" is a sequence to stair 4 plus that move; every sequence ending with "2" is a sequence to stair 3 plus that move. The two groups don't overlap (different last move), and they cover everything. So

With ways(0) = 1 (the empty sequence: you are already there) and ways(1) = 1:

0123456
ways (steps 1, 2)11235813
ways (steps 1, 2, 3)112471324

The first row is the Fibonacci sequence shifted by one (). The second row allows steps of 1, 2 or 3: each entry is the sum of the three before it (a "tribonacci" sequence). With allowed step sizes, sum the previous entries — or keep a running window sum of the last values so each step is even for large (a trick from Prefix Sums and Sliding Window).

That single question — "what was the last decision?" — is how every recurrence on this page is born.

Optimising by the last decision

Change the question: each house on a street holds some money, , and you may not rob two neighbouring houses (the alarm links them). What is the most you can take?

Look at the last house, house 4 (money 1). Either you rob it or you don't.

  • Skip it: the best you can do is the best for houses 0–3.
  • Rob it: then house 3 is forbidden, and the best is (best for houses 0–2) + 1.

So best(0..4) = max(best(0..3), best(0..2) + a[4]). Again, only the two previous answers matter. You have never needed to remember which houses were robbed, only the two best totals.

What "state" means here

A state is the summary of the past that the future needs. For climbing stairs it is "which stair am I on". For house robber it is "how many houses have I considered". For stock trading it is "which day is it and am I holding a share". The art of 1D DP is choosing a state that is small (one index, maybe plus a flag) but complete (the future truly doesn't need anything else). If you discover the future needs more — "how many transactions are left", "how much capacity is left" — you add that as a dimension.

Rolling variables: why the table disappears

If dp[i] reads only dp[i-1] and dp[i-2], then once you have computed dp[i], the value dp[i-2] is never read again. Keep two variables, prev2 and prev1, and slide them:

cur = f(prev1, prev2, a[i])
prev2, prev1 = prev1, cur

Memory drops from to . The catch, as in Grid DP: once the old values are gone, you cannot walk back to reconstruct which choices were made. Keep the full array if you need the choices.

Mechanics

1. Fibonacci and climbing stairs

State: ways[i] = number of move sequences that reach stair exactly. Transition: ways[i] = ways[i-1] + ways[i-2] (or the sum of the last for step sizes; with an arbitrary set of step sizes , ). Base: ways[0] = 1. Order: .

graph LR
    S3["stair 3: 3 ways"] -->|"+2"| S5["stair 5: 3 + 5 = 8 ways"]
    S4["stair 4: 5 ways"] -->|"+1"| S5

The naive recursion ways(n) = ways(n-1) + ways(n-2) without memoisation makes calls (, the golden ratio): ways(40) makes over 300 million calls. Memoised or tabulated, it is additions.

Deeper: faster than linear

grows like , so its digit count is linear in ; computing it exactly is never truly bit operations. Modulo a prime, though, the recurrence is a 2×2 matrix power, , computable in multiplications by repeated squaring. Any linear recurrence with terms becomes a matrix power in . That is the subject of Matrix Exponentiation.

2. Min cost climbing stairs

Each stair has a cost that you pay when you step off it. You start on stair 0 or stair 1 for free, climb 1 or 2 at a time, and want to reach the "top", which is one past the last stair.

State: dp[i] = cheapest cost to stand on position (with position = the top). Transition: dp[i] = min(dp[i-1] + c[i-1], dp[i-2] + c[i-2]). Base: dp[0] = dp[1] = 0 (free start).

On : dp[2] = min(0 + 15, 0 + 10) = 10, dp[3] = min(10 + 20, 0 + 15) = 15. Answer 15: start on stair 1, pay 15, jump two to the top.

On the longer the table is 0 0 1 2 2 3 3 4 4 5 6, answer 6: every 100 gets jumped over.

3. House robber (a line of houses)

State: best[i] = most money from houses with no two adjacent robbed. Transition: best[i] = max(best[i-1], best[i-2] + a[i]) — skip house , or rob it on top of the best that ends two houses back. Base: best[-1] = best[-2] = 0 (no houses, no money). In rolling form: prev2 = prev1 = 0. Answer: best[n-1] (or 0 for an empty street).

Dry run on with rolling variables (prev2 = best two houses back, prev1 = best one house back):

ia[i]prev2prev1rob: prev2 + a[i]skip: prev1best[i]
0200202
1702727
292711711
33711101111
411111121112

Answer 12: rob houses 0, 2 and 4 (). Notice row 3: robbing house 3 gives 10, but skipping keeps 11, so the DP skips it — and then row 4 can rob house 4 on top of 11.

A common wrong idea is "take all even-indexed houses or all odd-indexed houses". On , evens give 3, odds give 3, but robbing houses 0 and 3 gives 4. The DP finds it; the parity trick doesn't.

graph LR
    B2["best[i-2]"] -->|"rob house i: + a[i]"| BI["best[i] = max(...)"]
    B1["best[i-1]"] -->|"skip house i"| BI

4. House robber II (a circle of houses)

Now the street is a circle: house and house are neighbours. The linear DP breaks because it has no way to know, when it reaches the last house, whether house 0 was robbed.

The fix is a case split on a single decision. In any valid plan, house 0 and house are not both robbed. So at least one of them is skipped:

  • Case A: house is skipped. Then the circle is just the line .
  • Case B: house is skipped. Then it is the line .

Every valid plan falls in case A or case B (or both), and every plan in either case is valid on the circle. So the answer is max(rob(a[0..n-2]), rob(a[1..n-1])), with the special case (the single house is its own neighbour only in a degenerate sense; LeetCode's convention is that you may rob it).

On as a circle: case A on gives 11 (houses 0 and 2); case B on gives 10. Answer 11 — the linear answer 12 used both house 0 and house 4, which are now neighbours. On : case A gives 3, case B gives 3, answer 3.

The general trick: break a cycle by fixing one decision

"Circular" 1D DPs (circular house robber, maximum circular subarray, circular arrangements) are usually solved by running the linear DP a constant number of times, each time with one boundary decision fixed. It works whenever the circle only adds one extra constraint between the first and last element.

5. House robber III (a tree) — a pointer

If the houses form a binary tree and "adjacent" means parent–child, the line becomes a tree, and "the previous two answers" become "the answers of my children". Each node returns a pair: (best in my subtree if I am robbed, best if I am not). If I am robbed, my children must not be: rob = val + skip(left) + skip(right). If I am not, each child picks its better option: skip = max(left) + max(right). One post-order traversal, . That is the gateway problem of Tree DP; for traversals see Binary Trees & Traversals.

6. Delete and earn (house robber in disguise)

You get a list of numbers. Picking a number earns points, but deletes every copy of and . Maximise points.

Two observations turn this into house robber:

  1. If you pick one copy of , you should pick all copies (the neighbours are already deleted; the other copies are free money). So the earning for value is points[x] = x * count(x).
  2. Picking value forbids values and : exactly "no two adjacent", with adjacency on the value line.

On : points = [0, 0, 4, 9, 4] for values 0..4. House robber on that gives 9 (take all the 3s), which beats (the 2s and the 4). If the values are huge and sparse (say up to ), sort the distinct values instead of bucketing: consecutive distinct values are "adjacent" only if , otherwise you can freely take both.

7. Decode ways (careful with '0')

A message of letters A–Z is encoded as numbers: A → 1, B → 2, …, Z → 26. Given a digit string, how many ways can it be decoded? "226" → 2 2 6 (BBF), 22 6 (VF), 2 26 (BZ): 3 ways.

Last-decision question: the last letter came either from the last one digit or the last two digits.

  • One digit s[i-1] is a valid letter iff it is '1'–'9'. '0' alone is not a letter.
  • Two digits s[i-2..i-1] are a valid letter iff they form 10–26. "05" is not a letter (no leading zeros), and neither is "27".

State: dp[i] = number of decodings of the first characters. Transition: dp[i] = (s[i-1] != '0' ? dp[i-1] : 0) + (10 <= int(s[i-2..i-1]) <= 26 ? dp[i-2] : 0). Base: dp[0] = 1 (the empty prefix has one decoding: nothing). This is the "empty sequence" base, same as climbing stairs.

Dry run on "11106":

is[i-1]last twoone-digit parttwo-digit partdp[i]
0————1
11—dp[0] = 1—1
2111dp[1] = 1dp[0] = 12
3111dp[2] = 2dp[1] = 13
4010'0' alone invalid → 0dp[2] = 22
5606dp[4] = 2"06" invalid → 02

Answer 2: 1 1 10 6 (AAJF) and 11 10 6 (KJF). Row 4 is where the zero bites: the 0 must be glued to the 1 before it, which kills every decoding that used that 1 as a letter by itself.

The zero cases worth memorising (each is a test in the code below):

InputAnswerWhy
"06"0A leading zero can never be decoded
"10"1Only 10 (J)
"100"0The second 0 can attach to nothing valid ("00" is not a letter)
"2101"12 10 1 only: 21 0 1 fails on the lone zero
"1201234"31 20 1 2 3 4, 1 20 12 3 4, 1 20 1 23 4

8. Maximum subarray (Kadane's algorithm as DP)

Find the largest sum of a contiguous, non-empty subarray. For the answer is 6, from .

The trick is choosing the right state. "Best subarray within the first elements" does not have a clean recurrence: knowing the best so far doesn't tell you whether can extend it. Instead pin one end:

State: end[i] = largest sum of a subarray that ends exactly at . Transition: a subarray ending at is either alone, or a subarray ending at extended by . The best of the second kind is end[i-1] + a[i]. So

Answer: (every subarray ends somewhere).

In words: if the best run ending just before me is negative, drop it and start fresh at me.

ia[i]end[i-1] + a[i]end[i]best so far
0−2—−2−2
11−11 (restart)1
2−3−2−21
3424 (restart)4
4−1334
52555
61666
7−5116
84556

The run that wins starts at index 3 (the last restart before the best) and ends at index 6. To report the indices, remember where the current run started whenever you restart, and copy it when best improves.

Proof of correctness (induction on ). Claim: after processing index , end equals the true maximum over all subarrays ending at , and best equals the true maximum over all subarrays ending at or before .

  • Base (): the only subarray ending at 0 is , so end = best = a[0] is right.
  • Step: let be any subarray ending at . If , its sum is . Otherwise where ends at ; by the induction hypothesis , so . Hence every subarray ending at has sum , and both values are achieved by actual subarrays (, and the optimal extended). So end[i] is exactly the maximum. best is then the max of the old best (subarrays ending before ) and end[i] (ending at ), which covers every subarray ending at or before . ∎

This is the same "cut and paste" optimal-substructure argument as in CLRS §14.3, specialised to a single index.

All-negative arrays

If every number is negative, the answer is the largest single element (the subarray must be non-empty). Initialising best = 0 returns 0 — wrong. Initialise end = best = a[0] and start the loop at 1. (Some problems allow the empty subarray; then 0 is correct. Read the statement.)

9. Maximum product subarray

Same question with products. The twist: a negative number turns the smallest product into the largest. . So the best product ending at may come from the worst (most negative) product ending at .

State: two values per index, hi[i] and lo[i] = largest and smallest products of a subarray ending at . Transition: the candidates are alone, hi[i-1]·a[i] and lo[i-1]·a[i]:

Dry run on :

ia[i]hi[i]lo[i]best
02222
1−5−5−102
2−220 (from lo = −10)−220
3−48−8020
4324−24024

Answer 24 from . The table shows the min doing real work: at , the 20 comes from . A zero resets both to 0, which the " alone" candidate handles: right after a zero, alone beats whenever .

10. Jump game: DP versus greedy

a[i] is the maximum jump length from index . Can you reach the last index from index 0?

DP view. good[i] = "from you can reach the end". Fill right to left: good[n-1] = true, and good[i] = any(good[j] for j in i+1 .. i+a[i]). That is , up to . On every index is good; on only index 4 is (everything funnels into the 0 at index 3).

Greedy view. Walk left to right keeping reach = the furthest index reachable so far. If you ever stand at , you are stuck. Otherwise reach = max(reach, i + a[i]). , space.

Why the greedy is allowed. The set of indices reachable from 0 is always a prefix : if you can reach index , you can reach every too (the jump that crossed over could have been shortened to land on it, since you may jump up to ). So a single number — the right end of that prefix — is a complete state. The DP keeps a boolean per index; the greedy notices those booleans are always a run of trues followed by falses, and stores only the boundary.

This is a pattern worth recognising: when the DP table has a monotone shape, a greedy that tracks only the boundary is the DP with the redundancy removed. The general theory of when greedy is safe is in Greedy Algorithms.

Jump Game II (minimum number of jumps) has the same split: the DP jumps[j] = min(jumps[i] + 1) over that can reach is ; on it gives [0, 1, 1, 2, 2], answer 2. The greedy version is a BFS by "levels": all indices reachable with jumps form a contiguous range, and the next range ends at the furthest jump from the current one.

11. The stock family as a state-machine DP

You get daily prices . You may hold at most one share at a time. Different rules give six classic problems. The brute force (try every pattern of buy/sell days) is exponential; the DP is "one day at a time, a few states per day".

The state machine. On each day you are in one of a few states. The transitions between states are buy, sell or rest, and each changes your cash.

stateDiagram-v2
    [*] --> Rest
    Rest --> Rest: wait
    Rest --> Hold: buy, pay price
    Hold --> Hold: wait
    Hold --> Sold: sell, get price
    Sold --> Rest: forced cooldown day

For each state keep the most cash you can have at the end of day while in that state (holding a share counts its purchase price as already paid, so hold is usually negative). Each day, compute the new values from the old ones along the arrows:

ProblemStatesTransitions per dayAnswer
One transaction (LC 121)hold, cashhold = max(hold, -p), cash = max(cash, hold + p)cash
Unlimited (LC 122)hold, cashhold = max(hold, cash - p), cash = max(cash, hold + p)cash
Cooldown (LC 309)hold, sold, resthold' = max(hold, rest - p), sold' = hold + p, rest' = max(rest, sold)max(sold, rest)
Fee (LC 714)hold, cashhold = max(hold, cash - p), cash = max(cash, hold + p - fee)cash
At most (LC 123/188)buy[j], sell[j] for buy[j] = max(buy[j], sell[j-1] - p), sell[j] = max(sell[j], buy[j] + p)sell[k]

The only difference between "one transaction" and "unlimited" is where a buy comes from: with one transaction you buy from zero cash (-p), with unlimited you buy from whatever you have already earned (cash - p).

Answers on the standard examples (all computed by the test script):

PricesRuleAnswerOne optimal plan
7 1 5 3 6 4one transaction5buy at 1, sell at 6
7 1 5 3 6 4unlimited71→5 (+4), 3→6 (+3)
1 2 3 0 2cooldown3buy 1, sell 2, cool, buy 0, sell 2
1 3 2 8 4 9fee 281→8 (+7−2), 4→9 (+5−2)
3 2 6 5 0 3at most 272→6 (+4), 0→3 (+3)
3 3 5 0 0 3 1 4at most 260→3 (+3), 1→4 (+3)

Dry run: cooldown on . After you sell, you must rest one day before buying again. The three states at the end of day : hold (own a share), sold (sold today, so tomorrow is a cooldown), rest (no share, free to buy tomorrow). Start: hold = sold = −∞ (impossible before day 0), rest = 0. All three new values are computed from the old values of the previous day.

DayPricehold = max(hold, rest − p)sold = hold + prest = max(rest, sold)
01max(−∞, 0 − 1) = −1−∞0
12max(−1, 0 − 2) = −1−1 + 2 = 1max(0, −∞) = 0
23max(−1, 0 − 3) = −1−1 + 3 = 2max(0, 1) = 1
30max(−1, 1 − 0) = 1−1 + 0 = −1max(1, 2) = 2
42max(1, 2 − 2) = 11 + 2 = 3max(2, −1) = 2

Answer max(sold, rest) = 3. Day 3 is the interesting one: hold becomes 1 by buying at price 0 with rest = 1 — the cash from selling on day 1 (at price 2), which became "rest" on day 2 after the forced cooldown. Then day 4 sells for .

The cooldown is entirely encoded in the arrow sold → rest: there is no arrow sold → hold, so you cannot buy the day after selling.

Deeper: why means "unlimited"

A profitable transaction needs a buy day strictly before a sell day, and transactions don't overlap, so at most of them fit in days. If , the "at most " limit can never bind, and the unlimited solution (sum of all positive day-to-day increases) is correct. Without this shortcut, a huge (say ) makes the DP allocate and loop over far more layers than can ever be used.

The ladder: brute force → better → optimal

Take house robber as the running example.

Rung 1: try every subset

Every plan is a subset of houses with no two adjacent. Enumerate all subsets, discard invalid ones, keep the best.

def rob_brute(a):
    n, best = len(a), 0
    for mask in range(1 << n):
        if mask & (mask >> 1):            # two adjacent bits set: alarm
            continue
        best = max(best, sum(a[i] for i in range(n) if mask >> i & 1))
    return best


assert rob_brute([2, 7, 9, 3, 1]) == 12
assert rob_brute([2, 1, 1, 2]) == 4

time. At that is about operations. Its value is as a test oracle (this lesson's code was checked against it on random inputs). The valid subsets are counted by Fibonacci numbers — of them — so even skipping invalid masks cleverly is still exponential.

Rung 2: plain recursion on the last decision

def rob_rec(a, i=None):
    if i is None:
        i = len(a) - 1
    if i < 0:
        return 0
    return max(rob_rec(a, i - 1), rob_rec(a, i - 2) + a[i])

This is the recurrence, with no memory. It makes calls (the call tree is the Fibonacci tree). Better than only by a constant in the exponent.

Rung 3: memoize (top-down)

Cache rob_rec(i): distinct arguments, work each, time, memory and recursion depth (Python's default limit of about 1000 frames breaks at ).

Rung 4: tabulate (bottom-up array)

Fill best[0..n-1] left to right. time, space, no recursion, and the array lets you reconstruct the robbed houses by walking back: house was robbed iff best[i] != best[i-1].

Rung 5: rolling variables

Keep prev2, prev1. time, space. This is the version in the Implementation section.

RungMethodTimeExtra spaceWhy it beats the rung above
1All subsetsBaseline; obviously correct
2Plain recursion stackOnly explores valid plans
3Memoized recursion + stackEach prefix solved once
4TabulationNo recursion limit, supports reconstruction
5Rolling variablesSame speed, constant memory

The same ladder applies to every problem here. For Kadane, rung 1 is "all subarrays, each summed in " (); rung 2 uses prefix sums to get ; divide and conquer gives (Bentley's intermediate solution, see Divide & Conquer); Kadane gives , .

Correctness

Every algorithm on this page is proved the same way: induction over the index, with the inductive step being an exhaustive, disjoint case split on the last decision.

Climbing stairs. Sequences reaching are partitioned by their last move. Moves of size are in bijection with sequences reaching . Disjoint (different last move), exhaustive (no other moves), so the sum is exact. ways[0] = 1 counts the empty sequence, which is what makes ways[2] = ways[1] + ways[0] = 2 (the plans "1,1" and "2").

House robber. Let OPT be the best for houses . Consider an optimal plan for . If skips house , it is a valid plan for , so OPT OPT. If robs house , it skips house , and is a valid plan for , so OPT OPT. Conversely both values are achievable (an optimal plan for is valid for ; an optimal plan for plus house is valid since is unused). So OPT equals the max. This needs only to justify "skip" being allowed; it holds even with negative values.

Circular house robber. Shown above by the case split: the valid circular plans are exactly the union of the valid linear plans on and on .

Decode ways. Decodings of the prefix of length are partitioned by the length of the last letter's code (1 or 2 digits), and a decoding with last code of length is a decoding of the prefix of length followed by a valid code. The validity tests (no lone 0, two-digit codes in 10–26) are exactly the alphabet's rules, so the sum is exact.

Kadane. Proved in full above.

Maximum product. Same as Kadane, with one extra fact: for a fixed , the map is increasing if and decreasing if . So the extreme values of over all products of subarrays ending at are attained at the extreme values of — that is, at hi[i-1] or lo[i-1]. Keeping both extremes is therefore enough.

Jump game greedy. Invariant: after processing indices (all of them reachable), reach is the largest index reachable using jumps that start at . Since the reachable set is a prefix (argued above), index is reachable iff . If not, nothing beyond is reachable either, so returning false is correct.

Stock state machines. A trading plan is a path through the state machine, one arrow per day, and its profit is the sum of the arrow weights ( for buy, for sell, for wait/cooldown, per sale). The DP computes, for each (day, state), the maximum-weight path ending there — a longest path in a DAG whose layers are days (see Topological Sort and DAG DP). Correctness is the usual induction over days: every path to (day , state ) arrives from (day , some predecessor of ), and the max over predecessors of (best path there + arrow weight) is exactly the formula.

Complexity

ProblemTimeSpace (array)Space (rolling)Note
Climbing stairs, step sizes with a running window sum (consecutive sizes )
Fibonacci mod by matrix power
Min cost climbing stairs
House robber I / IIII runs I twice
House robber III (tree) stack— = tree height
Delete and earn— = max value; by sorting if is huge
Decode ways
Kadane / max product—
Jump game (DP / greedy) / / —— /
Stocks: 1, unlimited, cooldown, fee—2 or 3 states per day
Stocks: at most — if

All linear-time ones are optimal: any correct algorithm must read every input element (changing one price or house value can change the answer).

Integer sizes. Climbing-stairs counts grow like : they overflow signed 32-bit at () and signed 64-bit at (). Decode-ways counts can grow the same way ("1111…" gives Fibonacci numbers). Maximum product can overflow 64-bit if the problem does not bound it; LeetCode 152 guarantees the answer fits in 32 bits, but intermediate lo values may not — use 64-bit or double for the running products.

Implementation

Two code groups: house robber I & II first, then decode ways and stock with cooldown. Each block runs its own tests on this lesson's examples. They were also checked against the brute-force oracles (all subsets for house robber, all segmentations for decode ways, a memoised search over (day, holding) for cooldown) on hundreds of random inputs.

House robber I and II

from typing import List


def rob_line(a: List[int]) -> int:
    """Max money from a line of houses, never robbing two neighbours."""
    prev2, prev1 = 0, 0                   # best up to i-2, best up to i-1
    for x in a:
        prev2, prev1 = prev1, max(prev1, prev2 + x)   # skip i, or rob i on top of best(i-2)
    return prev1


def rob_circle(a: List[int]) -> int:
    """Houses in a circle: first and last are neighbours."""
    if len(a) == 1:
        return a[0]
    return max(rob_line(a[:-1]), rob_line(a[1:]))     # drop the last, or drop the first


if __name__ == "__main__":
    assert rob_line([2, 7, 9, 3, 1]) == 12
    assert rob_line([2, 1, 1, 2]) == 4
    assert rob_line([]) == 0
    assert rob_line([5]) == 5
    assert rob_circle([2, 3, 2]) == 3
    assert rob_circle([1, 2, 3, 1]) == 4
    assert rob_circle([2, 7, 9, 3, 1]) == 11
    assert rob_circle([5]) == 5
    print("house robber tests passed")
public class HouseRobber {
    /** Max money from houses a[lo..hi] (inclusive) in a line. */
    static long robLine(int[] a, int lo, int hi) {
        long prev2 = 0, prev1 = 0;               // best up to i-2, best up to i-1
        for (int i = lo; i <= hi; i++) {
            long cur = Math.max(prev1, prev2 + a[i]);   // skip i, or rob i
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    static long robLine(int[] a) {
        return robLine(a, 0, a.length - 1);
    }

    static long robCircle(int[] a) {
        int n = a.length;
        if (n == 1) return a[0];
        return Math.max(robLine(a, 0, n - 2), robLine(a, 1, n - 1));   // drop last, or drop first
    }

    public static void main(String[] args) {
        check(robLine(new int[]{2, 7, 9, 3, 1}) == 12);
        check(robLine(new int[]{2, 1, 1, 2}) == 4);
        check(robLine(new int[]{}) == 0);
        check(robLine(new int[]{5}) == 5);
        check(robCircle(new int[]{2, 3, 2}) == 3);
        check(robCircle(new int[]{1, 2, 3, 1}) == 4);
        check(robCircle(new int[]{2, 7, 9, 3, 1}) == 11);
        check(robCircle(new int[]{5}) == 5);
        System.out.println("house robber tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

// Max money from houses a[lo..hi] (inclusive) in a line.
long long robLine(const vector<int>& a, int lo, int hi) {
    long long prev2 = 0, prev1 = 0;               // best up to i-2, best up to i-1
    for (int i = lo; i <= hi; i++) {
        long long cur = max(prev1, prev2 + a[i]); // skip i, or rob i
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

long long robLine(const vector<int>& a) { return robLine(a, 0, (int)a.size() - 1); }

long long robCircle(const vector<int>& a) {
    int n = a.size();
    if (n == 1) return a[0];
    return max(robLine(a, 0, n - 2), robLine(a, 1, n - 1));   // drop last, or drop first
}

int main() {
    assert(robLine({2, 7, 9, 3, 1}) == 12);
    assert(robLine({2, 1, 1, 2}) == 4);
    assert(robLine(vector<int>{}) == 0);
    assert(robLine({5}) == 5);
    assert(robCircle({2, 3, 2}) == 3);
    assert(robCircle({1, 2, 3, 1}) == 4);
    assert(robCircle({2, 7, 9, 3, 1}) == 11);
    assert(robCircle({5}) == 5);
    cout << "house robber tests passed\n";
    return 0;
}
function robLine(a: number[], lo = 0, hi = a.length - 1): number {
  let prev2 = 0, prev1 = 0; // best up to i-2, best up to i-1
  for (let i = lo; i <= hi; i++) {
    const cur = Math.max(prev1, prev2 + a[i]); // skip i, or rob i
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

function robCircle(a: number[]): number {
  const n = a.length;
  if (n === 1) return a[0];
  return Math.max(robLine(a, 0, n - 2), robLine(a, 1, n - 1)); // drop last, or drop first
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

check(robLine([2, 7, 9, 3, 1]) === 12);
check(robLine([2, 1, 1, 2]) === 4);
check(robLine([]) === 0);
check(robLine([5]) === 5);
check(robCircle([2, 3, 2]) === 3);
check(robCircle([1, 2, 3, 1]) === 4);
check(robCircle([2, 7, 9, 3, 1]) === 11);
check(robCircle([5]) === 5);
console.log("house robber tests passed");

The circular version passes index ranges instead of slicing in Java, C++ and TypeScript to avoid copying the array twice; Python slices for readability (two copies, which does not change the complexity).

Decode ways and stock with cooldown

from typing import List


def num_decodings(s: str) -> int:
    """Ways to decode a digit string with A=1 ... Z=26."""
    prev2, prev1 = 0, 1                   # dp[i-1], dp[i]; dp[0] = 1 (empty prefix)
    for i, ch in enumerate(s):
        cur = prev1 if ch != "0" else 0   # last letter uses one digit (not '0')
        if i > 0 and (s[i - 1] == "1" or (s[i - 1] == "2" and ch <= "6")):
            cur += prev2                  # last letter uses two digits, 10..26
        prev2, prev1 = prev1, cur
    return prev1


def max_profit_cooldown(prices: List[int]) -> int:
    """Unlimited trades, one share at a time, one rest day after every sale."""
    NEG = float("-inf")
    hold, sold, rest = NEG, NEG, 0        # best cash at end of day in each state
    for p in prices:
        hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
    return max(sold, rest)


if __name__ == "__main__":
    cases = {"226": 3, "11106": 2, "06": 0, "10": 1, "100": 0, "2101": 1,
             "1201234": 3, "12": 2, "27": 1, "0": 0}
    for s, want in cases.items():
        assert num_decodings(s) == want, (s, num_decodings(s))
    assert max_profit_cooldown([1, 2, 3, 0, 2]) == 3
    assert max_profit_cooldown([7, 1, 5, 3, 6, 4]) == 5
    assert max_profit_cooldown([6, 1, 3, 2, 4, 7]) == 6
    assert max_profit_cooldown([1]) == 0
    assert max_profit_cooldown([]) == 0
    print("decode / cooldown tests passed")
public class DecodeCooldown {
    static long numDecodings(String s) {
        long prev2 = 0, prev1 = 1;                 // dp[i-1], dp[i]; dp[0] = 1
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            long cur = ch != '0' ? prev1 : 0;      // one-digit letter (not '0')
            if (i > 0) {
                char pr = s.charAt(i - 1);
                if (pr == '1' || (pr == '2' && ch <= '6')) cur += prev2;   // two-digit letter 10..26
            }
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    static int maxProfitCooldown(int[] prices) {
        final int NEG = Integer.MIN_VALUE / 2;     // "impossible", safe to add a price to
        int hold = NEG, sold = NEG, rest = 0;
        for (int p : prices) {
            int nHold = Math.max(hold, rest - p);
            int nSold = hold + p;
            int nRest = Math.max(rest, sold);
            hold = nHold;
            sold = nSold;
            rest = nRest;
        }
        return Math.max(sold, rest);
    }

    public static void main(String[] args) {
        String[] in = {"226", "11106", "06", "10", "100", "2101", "1201234", "12", "27", "0"};
        long[] want = {3, 2, 0, 1, 0, 1, 3, 2, 1, 0};
        for (int i = 0; i < in.length; i++) check(numDecodings(in[i]) == want[i]);
        check(maxProfitCooldown(new int[]{1, 2, 3, 0, 2}) == 3);
        check(maxProfitCooldown(new int[]{7, 1, 5, 3, 6, 4}) == 5);
        check(maxProfitCooldown(new int[]{6, 1, 3, 2, 4, 7}) == 6);
        check(maxProfitCooldown(new int[]{1}) == 0);
        check(maxProfitCooldown(new int[]{}) == 0);
        System.out.println("decode / cooldown tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long numDecodings(const string& s) {
    long long prev2 = 0, prev1 = 1;                // dp[i-1], dp[i]; dp[0] = 1
    for (size_t i = 0; i < s.size(); i++) {
        char ch = s[i];
        long long cur = ch != '0' ? prev1 : 0;     // one-digit letter (not '0')
        if (i > 0 && (s[i - 1] == '1' || (s[i - 1] == '2' && ch <= '6')))
            cur += prev2;                          // two-digit letter 10..26
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int maxProfitCooldown(const vector<int>& prices) {
    const int NEG = INT_MIN / 2;                   // "impossible", safe to add a price to
    int hold = NEG, sold = NEG, rest = 0;
    for (int p : prices) {
        int nHold = max(hold, rest - p);
        int nSold = hold + p;
        int nRest = max(rest, sold);
        hold = nHold, sold = nSold, rest = nRest;
    }
    return max(sold, rest);
}

int main() {
    vector<pair<string, long long>> cases = {{"226", 3}, {"11106", 2}, {"06", 0}, {"10", 1}, {"100", 0},
                                             {"2101", 1}, {"1201234", 3}, {"12", 2}, {"27", 1}, {"0", 0}};
    for (const auto& c : cases) assert(numDecodings(c.first) == c.second);
    assert(maxProfitCooldown({1, 2, 3, 0, 2}) == 3);
    assert(maxProfitCooldown({7, 1, 5, 3, 6, 4}) == 5);
    assert(maxProfitCooldown({6, 1, 3, 2, 4, 7}) == 6);
    assert(maxProfitCooldown({1}) == 0);
    assert(maxProfitCooldown({}) == 0);
    cout << "decode / cooldown tests passed\n";
    return 0;
}
function numDecodings(s: string): number {
  let prev2 = 0, prev1 = 1; // dp[i-1], dp[i]; dp[0] = 1
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    let cur = ch !== "0" ? prev1 : 0; // one-digit letter (not '0')
    if (i > 0 && (s[i - 1] === "1" || (s[i - 1] === "2" && ch <= "6"))) cur += prev2; // 10..26
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

function maxProfitCooldown(prices: number[]): number {
  let hold = -Infinity, sold = -Infinity, rest = 0;
  for (const p of prices) {
    [hold, sold, rest] = [Math.max(hold, rest - p), hold + p, Math.max(rest, sold)];
  }
  return Math.max(sold, rest);
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const cases: Array<[string, number]> = [["226", 3], ["11106", 2], ["06", 0], ["10", 1], ["100", 0],
  ["2101", 1], ["1201234", 3], ["12", 2], ["27", 1], ["0", 0]];
for (const [s, want] of cases) check(numDecodings(s) === want, s);
check(maxProfitCooldown([1, 2, 3, 0, 2]) === 3);
check(maxProfitCooldown([7, 1, 5, 3, 6, 4]) === 5);
check(maxProfitCooldown([6, 1, 3, 2, 4, 7]) === 6);
check(maxProfitCooldown([1]) === 0);
check(maxProfitCooldown([]) === 0);
console.log("decode / cooldown tests passed");

Two details worth copying. First, the three cooldown states are updated simultaneously from the previous day's values (tuple assignment in Python and TypeScript, temporaries in Java and C++); updating hold first and then using the new hold for sold would let you buy and sell on the same day. Second, "impossible" is in Python/TypeScript and INT_MIN / 2 in Java/C++, so adding one price can never overflow into a plausible-looking number.

Real-world uses

  • Finding high-scoring segments in DNA and protein sequences. Score each residue (e.g. hydrophobicity, or a log-likelihood ratio), then find the maximum-sum contiguous segment: Kadane is the core. Karlin and Altschul's 1990 statistics for such segments underpin BLAST's scores, and Ruzzo and Tompa (1999) extended the linear-time idea to find all maximal scoring subsequences.
  • Viterbi decoding. Every 2G/3G modem, many Wi-Fi and satellite links, and classic HMM speech recognisers run the Viterbi algorithm (1967): for each time step, for each of a small number of states, keep the best score of a path ending in that state. The stock-trading state machine is the same algorithm with three states and prices as weights. Map-matching in navigation apps (snapping noisy GPS points to roads) commonly uses an HMM with Viterbi too (Newson and Krumm, 2009).
  • Counting and choosing segmentations. Decode ways is the counting version of word segmentation: "how many ways can this string be split into dictionary pieces of length ?" Tokenisers that pick the most likely segmentation, such as the unigram model in SentencePiece (Kudo, 2018), run a Viterbi-style 1D DP over string positions. The general string version is in String DP.
  • Trading-system backtests with constraints. "Best possible profit with a fee / a cooldown / at most trades" is used as an upper bound ("oracle profit") to judge how much of the available movement a strategy actually captured. The DP is exact for one asset and one-share positions; real portfolios are a much harder optimisation.
  • Scheduling with rest constraints. Shift planners that forbid two consecutive night shifts, or ad schedulers that forbid showing the same ad in adjacent slots, are house-robber constraints on a line (circular for weekly rotations).
  • Signal processing. Maximum-subarray on a stream of (value − threshold) finds the most "unusual" window in sensor data or logs; it is a building block of CUSUM-style change detectors (Page, 1954), whose recurrence is Kadane's with the "start fresh" rule at zero.

Pitfalls & edge cases

  • Empty input. House robber on [] is 0; stock problems on [] are 0. Kadane's "non-empty subarray" is undefined on [] — decide and document.
  • Single element. Circular house robber with one house: return it (the two "drop one end" ranges would both be empty). Decode "0" is 0, "7" is 1.
  • Zeros in decode ways. A lone 0 is invalid; "30", "00", and leading 0 all kill a branch. Test "06", "10", "100", "2101", "27" every time.
  • Two-digit check by characters, not by int(s[i-2:i]) <= 26 alone. int("06") = 6 passes <= 26; you also need >= 10. The character test ('1' followed by anything, or '2' followed by '0'–'6') avoids that trap.
  • Kadane with best = 0. Wrong on all-negative arrays (see the warning above).
  • Max product: forgetting the min. [-2, 3, -4] should give 24; tracking only the max gives 3.
  • Stock states updated in place. Use the previous day's values for all states (simultaneous update). For the one-transaction and unlimited cases, updating cash after hold happens to be safe (it amounts to buying and selling on the same day, profit 0), but for cooldown and fee variants it can be wrong or confusing — just use temporaries.
  • Initialising hold = 0. That means "I hold a share I got for free". Use (or on day 0).
  • huge in "at most transactions". Switch to the unlimited solution when , or the DP times out and may allocate a huge array.
  • Overflow. Fibonacci-like counts overflow 32-bit at ; use 64-bit, big integers or the modulus.
  • Recursion depth. Memoised Python solutions fail around ; prefer tabulation or raise the limit knowingly.

Variations

  • Climbing stairs with forbidden stairs, or variable step sets. Set ways[i] = 0 on forbidden stairs; sum over allowed steps. CSES "Dice Combinations" is steps 1–6 mod .
  • Frog jumps. Cost for jumping from to , jumps up to : dp[i] = min over j in [i-K, i-1] of dp[j] + |h_i - h_j| (AtCoder DP A and B). With large and a cost that splits as , a monotonic deque gives .
  • Maximum circular subarray. Either the best subarray doesn't wrap (plain Kadane), or it wraps, and then it is "total minus the minimum subarray". Edge case: if all numbers are negative, the wrap formula gives the empty subarray; return the plain Kadane answer.
  • Maximum subarray with at most one deletion. Two states per index: best ending here with no deletion, and with one deletion used.
  • Maximum sum with no two adjacent and at most picks. Adds a dimension (dp[i][j]); this is now a knapsack-like DP.
  • Decode ways II. '*' stands for any digit 1–9; same recurrence with multiplicities, mod .
  • Kadane in 2D. Maximum-sum submatrix: fix a pair of rows, collapse columns to a 1D array with column sums, run Kadane: .
  • Stock with transactions and cooldown/fee combined. Multiply the state machine: layers of (hold, sold, rest).
  • Paint fence / paint house. "No two adjacent posts the same colour" or "at most two in a row": a 1D DP over posts with a few states per post (last colour, or same-as-previous / different).
  • Fibonacci mod for huge . Matrix exponentiation; or the Pisano period when is small.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Climbing Stairs (LeetCode 70) — Count ways to climb stairs with steps of 1 or 2. Teaches counting by the last move.

Hint

ways[i] = ways[i-1] + ways[i-2], ways[0] = ways[1] = 1. Two rolling variables.

2. Frog 1 (AtCoder DP Contest A) — A frog hops 1 or 2 stones ahead, paying the height difference; minimise the total. Teaches min-cost recurrences.

Hint

dp[i] = min(dp[i-1] + |h[i]-h[i-1]|, dp[i-2] + |h[i]-h[i-2]|). Frog 2 (problem B) allows up to stones.

3. Min Cost Climbing Stairs (LeetCode 746) — Pay a cost to leave each stair; start on stair 0 or 1; reach one past the end. Teaches careful base cases.

Hint

dp[0] = dp[1] = 0; dp[i] = min(dp[i-1] + c[i-1], dp[i-2] + c[i-2]); answer dp[n].

4. Dice Combinations (CSES 1633) — Count ordered sequences of dice throws (1–6) summing to , modulo . Teaches -step climbing with a modulus.

Solution
MOD = 10**9 + 7


def dice_combinations(n):
    ways = [1] + [0] * n
    for i in range(1, n + 1):
        ways[i] = sum(ways[i - d] for d in range(1, 7) if d <= i) % MOD
    return ways[n]


assert dice_combinations(3) == 4     # 1+1+1, 1+2, 2+1, 3

Note this counts ordered sequences; the knapsack lesson explains how loop order switches between ordered and unordered counts.

5. House Robber (LeetCode 198) — Max money from a line of houses, no two neighbours. Teaches the take/skip recurrence.

Hint

best = max(skip = best[i-1], take = best[i-2] + a[i]). The code above is a full solution.

6. Maximum Subarray (LeetCode 53) — Largest sum of a contiguous non-empty subarray. Teaches "best ending here" states.

Hint

end = max(x, end + x), best = max(best, end). Start from a[0], not 0.

7. Best Time to Buy and Sell Stock (LeetCode 121) and II (LeetCode 122) — One transaction vs unlimited. Teaches the two-state machine.

Hint

121: hold = max(hold, -p), cash = max(cash, hold + p). 122: buy from cash - p instead of -p (equivalently, sum all positive day-to-day differences).

8. House Robber II (LeetCode 213) — Houses in a circle. Teaches breaking a cycle by case split.

Hint

max(rob(a[0..n-2]), rob(a[1..n-1])), special-case .

9. Delete and Earn (LeetCode 740) — Picking deletes all . Teaches reductions to a known DP.

Solution
def delete_and_earn(nums):
    points = [0] * (max(nums) + 1)
    for x in nums:
        points[x] += x                    # take every copy of x together
    prev2 = prev1 = 0
    for p in points:                      # house robber over the value line
        prev2, prev1 = prev1, max(prev1, prev2 + p)
    return prev1


assert delete_and_earn([2, 2, 3, 3, 3, 4]) == 9
assert delete_and_earn([3, 4, 2]) == 6

10. Decode Ways (LeetCode 91) — Count decodings of a digit string. Teaches validity guards on transitions.

Hint

One-digit term only if the digit is not 0; two-digit term only for 10–26. The code above is a full solution.

11. Maximum Product Subarray (LeetCode 152) — Largest product of a contiguous subarray. Teaches carrying both extremes.

Solution
def max_product(a):
    hi = lo = best = a[0]
    for x in a[1:]:
        cands = (x, hi * x, lo * x)       # a negative x swaps the roles of hi and lo
        hi, lo = max(cands), min(cands)
        best = max(best, hi)
    return best


assert max_product([2, 3, -2, 4]) == 6
assert max_product([-2, 3, -4]) == 24
assert max_product([2, -5, -2, -4, 3]) == 24
assert max_product([-2, 0, -1]) == 0

12. Jump Game (LeetCode 55) and Jump Game II (LeetCode 45) — Reachability, then minimum jumps. Teaches when a DP collapses into a greedy.

Hint

55: track reach; fail if i > reach. 45: BFS by levels — end of the current level, far of the next; when i == end, jump count + 1 and end = far.

13. Best Time to Buy and Sell Stock with Cooldown (LeetCode 309) and with Transaction Fee (LeetCode 714) — Teaches adding states and arrow weights to the machine.

Hint

Cooldown: three states (hold, sold, rest), no arrow from sold to hold. Fee: two states, subtract the fee on each sale.

14. Best Time to Buy and Sell Stock IV (LeetCode 188) — At most transactions. Teaches layered states and the shortcut. (LeetCode 123 is the special case.)

Solution
def max_profit_k(k, prices):
    n = len(prices)
    if k >= n // 2:                       # the limit can never bind
        return sum(max(0, prices[i + 1] - prices[i]) for i in range(n - 1))
    buy = [float("-inf")] * (k + 1)       # buy[j]: holding, j-th transaction open
    sell = [0] * (k + 1)                  # sell[j]: not holding, j transactions done
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]


assert max_profit_k(2, [3, 2, 6, 5, 0, 3]) == 7
assert max_profit_k(2, [3, 3, 5, 0, 0, 3, 1, 4]) == 6
assert max_profit_k(1, [7, 1, 5, 3, 6, 4]) == 5

Updating buy[j] and then sell[j] in place on the same day is safe here: it can only add a buy-and-sell on the same day, which earns 0.

15. House Robber III (LeetCode 337) — Houses on a binary tree. Teaches the step from 1D to tree DP.

Hint

Post-order; each node returns (rob_me, skip_me). rob_me = val + skip(left) + skip(right), skip_me = max(left) + max(right).

Common mistakes & interview follow-ups

"Can you do it in O(1) space?" For every problem here, yes: two or three rolling variables (or for transactions). Mention that you lose the ability to reconstruct the choice sequence, and offer the array version if they want it.

"Now return which houses to rob (or which days to trade)." Keep the array; walk back from the end: house was robbed iff best[i] != best[i-1], then jump to . For stocks, store the argmax choice per (day, state) and backtrack.

"Why not just take every other house?" Show [2, 1, 1, 2]: alternation gives 3, the optimum is 4.

"Why does Kadane reset when the running sum goes negative, not when it decreases?" A decreasing but still positive prefix still helps whatever comes next; only a negative prefix hurts every extension. Formally, max(a[i], prev + a[i]) picks the restart exactly when prev < 0.

"Make maximum subarray work on a stream, or on many queries." Streaming: Kadane is already one-pass memory. Range queries with updates: a segment tree where each node stores (total, best prefix, best suffix, best) — the merge is Kadane's logic.

"Jump game: why is greedy correct?" Reachable indices form a prefix, so one number (reach) is a complete state. Interviewers like hearing the DP first and then the observation that collapses it.

"Stocks: what changes with a fee? With a cooldown? With ?" One arrow weight; one extra state; layers. Drawing the state machine on the whiteboard first makes all six variants the same code.

Mistakes interviewers watch for: best = 0 in Kadane; missing the lo in max product; '0' handling in decode ways; circular robber without the case; in-place state updates that read today's value instead of yesterday's; hold = 0 initialisation; overflow on counts.

Quick quiz

1. In the house-robber dry run on [2, 7, 9, 3, 1], why is best[3] = 11 and not 10?

Answer

Robbing house 3 gives best[1] + 3 = 7 + 3 = 10; skipping it keeps best[2] = 11. The max is 11 (skip).

2. How many decodings does "2101" have, and which zero rule removes the others?

Answer

One: 2 10 1 (BJA). Reading 21 as a letter leaves 0 alone, which is invalid; 01 is not a valid two-digit code either.

3. Kadane on [-3, -1, -2] returns what, and what does the buggy best = 0 version return?

Answer

The correct answer is −1 (the single element). The buggy version returns 0, which is the empty subarray — not allowed when the subarray must be non-empty.

4. In maximum product on [2, -5, -2, -4, 3], where does the value 20 at index 2 come from?

Answer

From lo[1] × a[2] = -10 × -2 = 20. Without tracking the minimum, you would miss it.

5. In the cooldown state machine, which missing arrow implements the cooldown?

Answer

There is no arrow from sold to hold. After a sale you must pass through rest (one day) before you can buy.

6. Why can circular house robber be solved with two linear runs?

Answer

In any valid circular plan, house 0 and house are not both robbed, so the plan is valid on the line or on the line . Conversely any plan valid on either line is valid on the circle. So the best circular plan is the better of the two linear optima.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 14 (dynamic programming, optimal substructure and the cut-and-paste argument). The 3rd edition's §4.1 covers maximum subarray by divide and conquer, with exercise 4.1-5 asking for the linear-time method.
  • Jon Bentley, Programming Pearls, 2nd ed. (2000), Column 8 "Algorithm Design Techniques" — the history of the maximum-subarray problem from to Kadane's .
  • Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — §6.1–6.2 (weighted interval scheduling: the same "take it or skip it" recurrence).
  • Steven Skiena, The Algorithm Design Manual, 3rd ed. (2020) — Chapter 10 (dynamic programming, with war stories).
  • A. J. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm", IEEE Transactions on Information Theory 13(2), 1967.
  • Walter L. Ruzzo and Martin Tompa, "A Linear Time Algorithm for Finding All Maximal Scoring Subsequences", ISMB 1999.
  • Samuel Karlin and Stephen F. Altschul, "Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes", PNAS 87(6), 1990.
  • Paul Newson and John Krumm, "Hidden Markov Map Matching Through Noise and Sparseness", ACM SIGSPATIAL GIS 2009.
  • E. S. Page, "Continuous Inspection Schemes", Biometrika 41(1/2), 1954 (CUSUM).
  • cp-algorithms, Introduction to Dynamic Programming.
  • AtCoder Educational DP Contest, problem list — problems A and B are 1D DPs.

Lessons: previous — DP Foundations · next — The Knapsack Family · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Recursion & Induction · Prefix Sums · Sliding Window · Greedy Algorithms · Grid DP · String DP · Segment Trees · Tree DP · Matrix Exponentiation.