House Robber

At each house you have two options: rob it and skip the previous one, or skip it and keep whatever you had. The best total up to house i is the larger of the best total up to house i minus one and the best total up to house i minus two plus the value of house i.

def rob(nums):
    previous, current = 0, 0
    for value in nums:
        previous, current = current, max(current, previous + value)
    return current


print(rob([2, 7, 9, 3, 1]))
print(rob([5, 1, 1, 5]))

The outputs are 12 and 10. In the first array the best plan is to rob houses of value 2, 9 and 1, which are not adjacent, giving twelve. In the second the best is the first and the last house, giving ten.

The mechanism is the two options covering every case. Either you rob the current house, in which case the previous one must be skipped, or you do not rob it, in which case the previous best stands. Since the two cases are exhaustive and disjoint, taking the larger is correct.

The trade-off to name is that the two variable version uses constant space, while the obvious table version uses space linear in the number of houses. As with the climbing stairs problem, the recurrence only needs the last two values, so the whole history is unnecessary unless you want to reconstruct which houses were robbed. The other point is that this is a good example of a problem where a greedy choice fails, because always robbing the richest house can block two good neighbours, and the dynamic program explores both options properly.

Split the problem into two linear versions. Since the first and last houses are adjacent, you cannot rob both, so you rob either the first house and not the last, or the last house and not the first. Take the better of the two answers.

def rob_range(nums, start, end):
    previous, current = 0, 0
    for i in range(start, end + 1):
        previous, current = current, max(current, previous + nums[i])
    return current


def rob_circle(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    return max(rob_range(nums, 0, len(nums) - 2),
               rob_range(nums, 1, len(nums) - 1))


print(rob_circle([2, 3, 2]))
print(rob_circle([1, 2, 3, 1]))

The outputs are 3 and 4. For the first array the two middle houses are worth three and the outer two are worth four together, but they are adjacent so only one can be taken, giving three. For the second, robbing the first and third houses gives four.

The mechanism is the case split. Every valid solution either includes the first house or it does not, and in the first case the last house must be excluded, which leaves exactly the linear problem on houses zero to n minus two. The second case is the mirror image, and the union of the two cases covers every possible solution.

The trade-off to name is that the circular version runs the linear algorithm twice, so the time cost doubles but the space cost does not, since each run uses constant space. The edge cases are worth stating: an empty circle gives zero and a single house gives that house, and a two house circle is really the same as the linear problem with two entries. This split idea is the standard way to break a circular constraint and it reappears in problems like the gas station and the maximum subarray in a circular array.