Problem statement
Given houses with non-negative values, determine the largest amount that can be taken without selecting adjacent houses.
The lawful route
At each house, retain only the best total before the previous house and the best total through the previous house. Choose whether the current value is included.
Invariant
The retained states always represent the optimal lawful total for their completed prefixes.
Proof vocabulary used
- Dynamic Programming
- State Carry-Over
- Decision Space
- Invariant
Complexity
Time O(n) · Space O(1)