Linear DP

A linear DP has one index and reads a fixed number of cells behind it. dp[i] depends on dp[i-1], maybe dp[i-2], occasionally on a window of the last k — never on a search back through everything. That bound is what makes the whole scan O(n): n states, constant work each, exactly the product from what DP actually is.

Derive the recurrence from the decision at i

Houses on a street hold a[0..n-1] rupees each and no two adjacent houses can be robbed. Standing at house i, there are two options and no third:

• Rob it. Then house i-1 is off limits, and the best you could have done through i-2 still stands: dp[i-2] + a[i].
• Skip it. Then you keep whatever was best through i-1: dp[i-1].

dp[i] = max(dp[i-1], dp[i-2] + a[i])

The recurrence is not an insight; it is the enumeration of a two-way decision, written down. Every linear DP comes out this way — list what can happen at i, write the best answer each option leaves behind, take the max.

Define the state precisely: dp[i] is the best total considering the first i+1 houses, whether or not house i was robbed. That "whether or not" is doing real work. If you define dp[i] as "the best total that robs house i", the recurrence needs a scan back over all earlier non-adjacent choices and the solution turns O(n^2). The looser definition is what keeps the transition to two reads.

Padding the front of the table with two cells turns both base cases into plain zeros: dp[0] and dp[1] both stand for "no houses yet", and after house k the answer sits at dp[k+1]. On a = [1, 5] the table ends as [0, 0, 1, 5] — dp[2] is the best through one house, dp[3] the best through two, and the answer is the last cell:

def rob(a):
    dp = [0, 0]                     # dp[k+1] = best through the first k houses
    for x in a:
        dp.append(max(dp[-1], dp[-2] + x))
    return dp[-1]

Roll the array into two variables

dp[i] reads only dp[i-1] and dp[i-2], so at most two cells are ever alive. Keep them in variables and the array disappears:

def rob(a):
    prev = prev2 = 0          # best through i-1, best through i-2
    for x in a:
        prev, prev2 = max(prev, prev2 + x), prev
    return prev

A padded dp table in which dp[4] reads only dp[3] and dp[2], with those two cells marked as the whole live state and redrawn below as the variables prev2 and prev100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

At n = 10^5 the array version allocates 10^5 slots — roughly 3.6 MB in CPython once the integer objects are counted: 800 KB for the array of pointers, plus 28 bytes for each of the 100,000 int objects it points at — and the rolled version keeps two. The time is identical; only the memory moves. The rule generalises: the space you need is the width of the dependency window, not the length of the scan. Row-rolling in a 2D table, covered in two sequences, is the same move one dimension up.

The cost of rolling is that you can no longer reconstruct which houses were robbed — the history is gone. Keep the array when the problem asks for the solution rather than its value.

Kadane, as a DP that names its state well

The largest sum of a contiguous subarray looks like it needs a different idea. It does not; it needs the right state.

The tempting definition, "dp[i] = the best subarray within the first i elements", does not compose. Knowing the best subarray somewhere to the left tells you nothing about whether element i can join it, because it might not touch position i-1 at all.

Fix the state to the best subarray ending exactly at i. Now composition is forced: a subarray ending at i either extends the one ending at i-1, or starts fresh at i.

end[i] = max(a[i], end[i-1] + a[i])
answer = max(end[0..n-1])

def max_subarray(a):
    best = end = a[0]
    for x in a[1:]:
        end = max(x, end + x)
        best = max(best, end)
    return best

Two things fall out of the framing. The answer is the maximum over all states, not the last state, because the best subarray ends somewhere. And extending beats restarting exactly when end[i-1] > 0 — the "reset when the running sum goes negative" rule, which is a consequence here rather than a trick to recall.

Starting from best = a[0] rather than 0 is what makes an all-negative array return its largest element instead of an empty sum. That is the single most common bug here.

Counting instead of optimising

Some linear DPs replace max with +. The transition structure is identical; the arithmetic changes, and so does the care needed at the boundary.

Climbing n stairs one or two steps at a time: dp[i] = dp[i-1] + dp[i-2], because the last move came from one of two places and those two sets of paths are disjoint. Disjointness is the precondition for adding — if the same arrangement can be reached down two branches, addition double counts.

Decoding a digit string where "A" is 1 and "Z" is 26 has the same shape with guards on each term. Let dp[i] be the number of decodings of the first i characters:

def decodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1                                  # the empty prefix has one decoding
    for i in range(1, n + 1):
        if s[i - 1] != '0':                    # one-digit letter, 1..9
            dp[i] += dp[i - 1]
        if i >= 2 and '10' <= s[i - 2:i] <= '26':
            dp[i] += dp[i - 2]                 # two-digit letter, 10..26
    return dp[n]

dp[0] = 1 is the base case people argue with. It is not "there is one way to decode nothing" as a philosophical claim — it is the multiplicative identity that makes dp[2] come out right when the first two digits form a single letter. Set it to 0 and every count collapses to 0.

The other boundary is the zero: "06" has no decodings, "10" has one, and both are silently wrong if you write s[i-2:i] <= '26' without the lower bound. Test "0", "06", "10", "100" and "226" — 0, 0, 1, 0 and 3 respectively — before you call it done.

In an interview

State the decision at i out loud before writing anything: "at each house I either rob it or skip it, so the state is the best total through i and the transition is a max of two terms." That sentence is the recurrence, and it is also the proof of correctness, since the two options are exhaustive.

When you finish, offer the space reduction unprompted: "it only ever reads two cells back, so I can roll it to O(1) space — though then I lose the ability to reconstruct which houses were chosen." Naming the trade-off beats doing it silently.

The mistake that loses points: getting the base cases wrong and patching them with if statements until the samples pass. Derive dp[0] and dp[1] from the definition of the state, then verify on the smallest input by hand — n = 0 and n = 1 — the way the solving loop asks you to test the edges.

Check yourself

Why is "the best subarray within the first i elements" a bad state for Kadane, and "the best subarray ending at i" a good one?

The first does not compose: it does not tell you whether the subarray touches position i-1, so you cannot decide whether a[i] can extend it. Ending at i pins the right edge, which makes the transition a two-way choice — extend or restart — and the answer becomes the max over all states.

You define dp[i] as "the best total that robs house i" instead of "the best total through house i". What happens to the transition and the complexity?

The transition becomes a maximum over every legal predecessor — a[i] + max(dp[j]) for all j at most i-2 — so each state does O(n) work and the scan is O(n^2). You can rescue it by carrying a running maximum of the earlier cells, but the looser state never has the problem: it reads two fixed cells.

In the decoding count, what breaks if you set dp[0] = 0?

Every cell collapses to 0. dp[1] is dp[0] = 0, dp[2] is dp[1] + dp[0] = 0, and the zeros propagate to the end, so the function reports that no string can be decoded. dp[0] = 1 is the empty product that lets the first letter — one digit or two — be counted once.