Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Quiet Vaults.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when House robber matches the clues
- 2Keep this true after every move: oneBack is the maximum reward from the processed prefix
- 3Reach the result within O(n) time and O(1) space
Rules and pressure
- Target cost: O(n) time and O(1) space
- State rule: oneBack is the maximum reward from the processed prefix
Lesson 1 of 3
Live algorithm trace
House robber
Complete execution1 of 6
Start with no selected vaults and reward zero.
1
twoBack = oneBack = 02
for each reward3
take = twoBack + reward4
skip = oneBack5
current = max(take, skip); shift6
return oneBacktwoBack = 0oneBack = 0
Truth to preserve / Cost target
Truth to preserve
oneBack is the maximum reward from the processed prefix
Cost target
O(n) time and O(1) space
For each vault, either skip it and keep the previous best, or take it after the best prefix ending two positions earlier.
Your call · What should guide every step of this algorithm?