House Robber
Hard · rating 1500 · dp
The first line contains n. The second line contains n non-negative integers (house values). Print the maximum total you can take without choosing two adjacent houses.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach (dynamic programming)
At each house you choose: skip it (keep the best total up to the previous house), or rob it (its value plus the best total up to two houses back, since adjacent houses can't both be robbed). Take the larger option.
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1Insight
Only the last two running totals ever matter, so the full DP table collapses to two variables.
Complexity
Time: O(n). Space: O(1).