Houses along a street hold nums[i] money each. You want to rob as much as possible, but robbing two adjacent houses on the same night sets off the alarm. Return the maximum amount you can rob.
1 + 3 = 4.2 + 9 + 1 = 12.- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every subset of non-adjacent houses, O(2^n). State: dp[i] = the best loot using only houses 0..i. Recurrence: either skip house i and keep dp[i - 1], or rob it and add nums[i] to dp[i - 2], so dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]). Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]). The recursion with memo is O(n), the bottom-up table is O(n) space, and two rolling variables bring it to O(1).
Algorithm
- Keep
prev2 = 0(best up toi - 2) andprev1 = 0(best up toi - 1). - For each house value
x, computecur = max(prev1, prev2 + x). - Shift:
prev2 = prev1,prev1 = cur. - Return
prev1.
O(n)Space: O(1)[2,1,1,2], where the best is 4 by robbing the first and last houses. Interviewers use exactly this to test whether you really need DP.class Solution: def rob(self, nums: List[int]) -> int: prev2, prev1 = 0, 0 # best up to i - 2, best up to i - 1 for x in nums: prev2, prev1 = prev1, max(prev1, prev2 + x) # skip x, or rob x return prev1