House Robber
You are a robber planning to rob houses along a street. Adjacent houses have security systems connected — robbing two adjacent houses triggers an alarm. Given an integer array `nums` representing the amount of money in each house, return the maximum amount you can rob without triggering the alarm. **Core Insight:** At each house you make a binary choice: rob it (and skip the previous) or skip it (and keep whatever you had through the previous house). Define `dp[i]` as the max money robbing up to house `i`. The recurrence is `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`. **Algorithm:** Space-optimised DP using two variables. Let `prev2` = max money up to two houses ago, `prev1` = max money up to the previous house. For each house: `curr = max(prev1, prev2 + nums[i])`, then shift `prev2 = prev1`, `prev1 = curr`. Return `prev1`. **Why it works:** `dp[i-2] + nums[i]` is the best you can do by robbing the current house; `dp[i-1]` is the best by skipping it. Taking the max of both gives the global optimum. **Complexity:** Time O(n) — one pass. Space O(1) — two variables.
Constraints
- •
1 ≤ nums.length ≤ 100 - •
0 ≤ nums[i] ≤ 400
def rob(nums: list[int]) -> int:
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1