House Robber

Take-or-skip recursion

At index i, make the choice literally:

• skip this house and solve from i + 1, or
• take its cash, force a skip over its neighbor, and solve from i + 2.

def rob(nums: list[int]) -> int:
    def best_from(i: int) -> int:
        if i >= len(nums):
            return 0
        skip = best_from(i + 1)
        take = nums[i] + best_from(i + 2)
        return max(skip, take)
 
    return best_from(0)

Both branches ask for the same suffixes again and again, which creates an exponential decision tree.

Time O(2ⁿ). Space O(n) for the recursion stack.

Rolling take-or-skip DP

Dynamic programming (DP) stores answers to recurring subproblems. Count houses from the left so the state doesn't need awkward negative indices:

• State: dp[i] is the largest total available from the first i houses.
• Transition: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]). The first term skips the current house; the second takes it.
• Base case: dp[0] = 0 and dp[1] = nums[0].

Only the previous two states feed the transition. Keep those two totals instead of the whole table.

def rob(nums: list[int]) -> int:
    two_houses_back = 0
    one_house_back = 0
 
    for cash in nums:
        current = max(one_house_back, two_houses_back + cash)
        two_houses_back = one_house_back
        one_house_back = current
 
    return one_house_back

Before each update, one_house_back is the best total if you skip the current house, while two_houses_back + cash is the best total if you take it. Choosing the larger preserves the optimal answer for the processed prefix.

Time O(n). Space O(1).