House Robber

01 · Question

You are given an integer array nums representing the amount of money of each house. You cannot rob adjacent houses. Return the maximum amount you can rob.

02 · Analysis

This iterative version keeps best totals for processed prefixes: rob1 ends before the previous house, rob2 includes the option of that house. For amount x, choose max(rob2, rob1+x), then shift the two saved results. The take/skip alternatives are exhaustive and never select adjacent houses. Nonnegative amounts, O(n) time, O(1) space; an empty input returns 0.

03 · Solution

Reference solution

1def rob(nums: List[int]) -> int:
2    rob1, rob2 = 0, 0
3    for x in nums:
4        newRob = max(rob1 + x, rob2)
5        rob1 = rob2
6        rob2 = newRob
7    return rob2

Climbing Stairs

Coin Change