Hints — p56 House Robber

Hint 1. At each house, you face a binary choice: rob it or skip it. The constraint links your choice at i to your choice at i-1. Sounds like… DP.

Hint 2. Define dp[i] = max money robbing among houses 0..i inclusive. What are the two ways to arrive at dp[i]?

Hint 3. Either (a) you skip house i, in which case dp[i] = dp[i-1]; or (b) you rob house i, in which case dp[i] = dp[i-2] + nums[i] (the i-2 because i-1 is now off-limits).

Hint 4. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

Hint 5. Notice dp[i] only needs dp[i-1] and dp[i-2]. Compress to two rolling variables prev1, prev2. O(n) time, O(1) space.

If stuck: see solution.py.