1-D linear DP

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Five houses in a row hold 2, 7, 9, 3 and 1 rupees. A thief may rob any houses but never two neighbours, because the alarms are linked. What is the most the thief can take? By hand you try combinations: 2 + 9 + 1 = 12, 7 + 3 = 10, 2 + 3 = 5, 7 + 1 = 8, 9 alone... The best is 12.

Trying combinations means, for each house, "rob or not", and 2⁵ = 32 choices here. For 100 houses that is 2¹⁰⁰, more than the number of grains of sand on Earth many times over. We need a way to reuse work instead of re-deciding every house for every combination.

Build the structure, one piece at a time

Piece one: a question with a small answer. Let dp[i] mean "the most you can take from houses 0 to i only". The final answer is dp[4].

Piece two: notice that the decision for house i has only two cases. Skip it: then the best is whatever the best was for houses 0 to i − 1, which is dp[i − 1]. Rob it: then house i − 1 is off limits and the best is nums[i] plus the best for houses 0 to i − 2, which is dp[i − 2]. Take the larger:

dp[i] = max( dp[i − 1], dp[i − 2] + nums[i] )

Piece three: fill the table from the left, because each entry needs the two before it.

Piece four: the table only ever looks back two places, so you do not need the whole array. Keep two variables, "best so far" and "best before that", and roll them forward.

Why it is correct

The invariant: after computing dp[i], it is the true best for the prefix ending at i. The base cases are right: dp[0] = nums[0], dp[1] = max of the two. For a larger i, any legal plan for houses 0 .. i either robs house i or not, and those two cases are exactly the two terms in the formula, each resting on a smaller prefix whose value is already correct. So the maximum of the two is the true best.

Why it is fast

Each entry costs one comparison and one addition, and there are n entries:

work = n steps, memory = 2 numbers

For 100 houses that is 100 steps instead of 2¹⁰⁰ combinations. The saving comes entirely from the fact that the best for a prefix does not depend on how it was achieved, only on its value.

How to recognise it in an interview

Cues: "cannot pick two adjacent", "ways to reach step n with steps of 1 or 2", "minimum cost to climb", anything where the answer for position i depends on positions i − 1 and i − 2 only. The first thing to say: "define dp[i] for the prefix, write the two-case recurrence, and roll two variables." House Robber is the example above. Climbing Stairs is the same shape with addition instead of max: ways[i] = ways[i − 1] + ways[i − 2], the Fibonacci numbers.

02The idea in one line

dp[i] from dp[i−1] and dp[i−2]; roll two variables.

Reach for it when: Climbing stairs, house robber, min cost climbing, decode ways, fibonacci.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: House Robber on [2,7,9,3,1]. These are its captions in order, so you can follow without the video or check a step you missed.

1. dp[i] = max(dp[i−1], dp[i−2] + nums[i]): skip house i or rob it
2. dp[0] = 2: only one house, rob it
3. dp[1] = max(2, 7) = 7
4. dp[2]: skip = 7, rob = 2 + 9 = 11 → 11
5. dp[3]: skip = 11, rob = 7 + 3 = 10 → 11
6. dp[4]: skip = 11, rob = 11 + 1 = 12 → 12
7. Answer is dp[4] = 12: rob houses 0, 2 and 4
8. Only dp[i−1] and dp[i−2] are needed: O(n) time, O(1) space

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).