How do you solve the house robber problem, where you cannot rob two adjacent houses?
At every house you have two choices. You rob it, and then you cannot rob the next one. Or you skip it and you keep whatever you had.
def rob(nums):
previous, current = 0, 0
for value in nums:
previous, current = current, max(current, previous + value)
return current
So how does it work? The two variables hold the best total up to the house before the current one and the best total up to the current one. At each house you take the bigger of two things. Either you skip this house and keep current, or you rob it and you get previous + value, because the house before this one has to be skipped.
the houses the best so far
-------------- --------------
2 2
7 7, because you cannot take both
9 12, because 2 and 9 are not next to each other
1 12
1 13
And the recurrence is this. The best total for the first n houses is the bigger of the best total for the first n minus one houses and the best total for the first n minus two houses plus the value of the nth house.
And there is a detail worth knowing about the two variables. Before the loop they are both zero, which is the answer for no houses at all. And the line previous, current = current, max(current, previous + value) works because Python works out the right-hand side first. So previous gets the old value of current and current gets the new best.
And the complexity is O of n for the time and O of 1 for the space. There is no table and no recursion.
So the rule to remember is this. At each house, rob it and skip the last one, or skip it and keep what you have.
The last question in this topic shows the circular version.