House Robber
Rolling DP — at each house, choose max of "skip" or "rob + value two back".
2 min read
dp array
Problem#
You can’t rob two adjacent houses. Maximize the total amount robbed.
Examples#
[1,2,3,1]→4.[2,7,9,3,1]→12.
Constraints#
1 <= nums.length <= 100.
Approach#
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Roll to two scalars.
Solution#
class Solution {public: int rob(vector<int>& nums) { int prev2 = 0, prev1 = 0; for (int v : nums) { int cur = max(prev1, prev2 + v); prev2 = prev1; prev1 = cur; } return prev1; }};func rob(nums []int) int { maxI := func(a, b int) int { if a > b { return a } return b } prev2, prev1 := 0, 0 for _, v := range nums { cur := maxI(prev1, prev2+v) prev2 = prev1 prev1 = cur } return prev1}from typing import List
class Solution: def rob(self, nums: List[int]) -> int: prev2 = prev1 = 0 for v in nums: prev2, prev1 = prev1, max(prev1, prev2 + v) return prev1function rob(nums) { let prev2 = 0, prev1 = 0; for (const v of nums) { const cur = Math.max(prev1, prev2 + v); prev2 = prev1; prev1 = cur; } return prev1;}class Solution { public int rob(int[] nums) { int prev2 = 0, prev1 = 0; for (int v : nums) { int cur = Math.max(prev1, prev2 + v); prev2 = prev1; prev1 = cur; } return prev1; }}function rob(nums: number[]): number { let prev2 = 0, prev1 = 0; for (const v of nums) { const cur = Math.max(prev1, prev2 + v); prev2 = prev1; prev1 = cur; } return prev1;}Editorial#
The choice at each house is binary: rob (then last robbed was at least two indices back) or skip (carry the previous max). Tracking only prev1 and prev2 is enough since the recurrence has a fixed lookback of 2.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#