1D DP
Include or skip the last house
Why it matters
Job selection, sensor placement, and maintenance scheduling can assign value to choices that may not be adjacent. Enumerating every allowed subset repeats the same prefixes and grows exponentially, even when only the best total matters. The maximum value must honor the no-adjacent rule without listing all valid selections.
Example
House Robber
nums[i] is cash in house i. Adjacent houses cannot both be robbed. Return the maximum loot.
- Input
- nums = [2, 7, 9, 3, 1]
- Output
- 12
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
House Robber
nums = [2, 7, 9, 3, 1]→12
The baseline, Try both choices recursively, is O(2ⁿ) · O(n). The better model below keeps this exact input and removes that bottleneck.
For [2, 7, 9, 3, 1], brute recursion repeats the same take-or-skip prefix subproblems. Carry only the previous two best totals: they progress to 2, 7, 11, 11, and 12, avoiding the exponential choice tree.
For [2, 7, 9, 3, 1], begin with prev = curr = 0. At 2, compare taking 0 + 2 with skipping 0, so curr becomes 2. At 7, compare 0 + 7 with 2, so the running best becomes 7.
At 9, taking it adds the best through house 0, 2 + 9 = 11, which beats 7. House 3 keeps 11; house 1 combines with the earlier 11 to make 12. Simultaneous assignment shifts old curr into prev before storing the new maximum.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.