Medium Include/Exclude Dynamic Programming
In plain English: Pick non-adjacent houses to rob so the total money is maximized.
At each house, choose the better of: rob it (skip previous) or skip it (keep previous best). Two variables track these rolling choices.
Prompt
Given an array of house values, find the maximum amount you can rob without robbing two adjacent houses.
Try to write it from scratch before scrolling down.
Solution
def rob(nums):
if not nums:
return 0
prev2, prev1 = 0, 0
for x in nums:
# include current + skip previous, or exclude current
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
# Test: rob([1,2,3,1]) == 4 (rob house 0 and 2)
# Test: rob([2,7,9,3,1]) == 12 (rob house 0, 2, 4)