House Robber

Problem statement

Houses sit in a line. nums[i] is the cash in house i. Adjacent houses have a shared alarm — you cannot rob two neighbors. Return the most you can steal.

Example:

Input:

nums = [2, 7, 9, 3, 1]

Expected output:

12

Why: rob houses 0, 2, and 4 → 2 + 9 + 1 = 12. Taking 7 + 3 + 1 is only 11.

Practice on LeetCode: House Robber

What we are choosing

At house i, if you take it, house i+1 is closed. The next house you are allowed to start from is i+2 or later.

house(i) means: rob i, then take the better of the two legal next starts:

house(i) = nums[i] + max(house(i+2), house(i+3))

Past the last house the take is 0. The last house alone is nums[n-1].

You do not need house(i+4) as a third choice. Amounts are non-negative, so skipping both i+2 and i+3 is never better than taking one of them and continuing.

The first house you rob is either 0 or 1. Answer is max(house(0), house(1)). Starting at 2 without 0 or 1 is dominated: adding a non-negative nums[0] on top of house(2) cannot hurt.

On the example:

house(4) = 1
house(3) = 3
house(2) = 9 + max(1, 0) = 10
house(1) = 7 + max(3, 1) = 10
house(0) = 2 + max(10, 3) = 12

max(12, 10) = 12.

Why not try every subset

Each house is take or skip, with the neighbor constraint. The raw tree is exponential, and house(3) is asked from both house(0) and house(1). There are only n starts. Remember each one.

The linear form of the same idea is dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip this house, or take it and skip the previous. Same answers, no call stack.

Golang Solution

memo[i] is the best total if you must rob house i. Uncomputed cells are -1 (zero is a legal take). After the last index, return 0. Compare starting at 0 and starting at 1.

Time: O(n) — each index is solved once
Space: O(n) — memo, plus O(n) recursion depth

func rob(nums []int) int {
    memo := make([]int, len(nums)+1)
    for i := 0; i < len(nums); i++ {
        memo[i] = -1
    }
    one := house(0, nums, memo)
    two := house(1, nums, memo)
    if one > two {
        return one
    }
    return two
}

func house(i int, nums, memo []int) int {
    if i >= len(nums) {
        return 0
    }
    if i == len(nums)-1 {
        return nums[i]
    }

    if memo[i] >= 0 {
        return memo[i]
    }

    memo[i] = nums[i] + max(house(i+2, nums, memo), house(i+3, nums, memo))

    return memo[i]
}

One house returns nums[0]: house(0) hits the last-house case, house(1) is past the end. Two houses return max(nums[0], nums[1]).