House Robber — Skip Adjacent DP

Problem

Rob houses in a row; cannot rob two adjacent houses. Maximize total.

Example: [2,7,9,3,1] → 12 (rob 2+9+1)

Approach — Skip Adjacent

prev2=0, prev1=0. For each house: curr = max(prev1, prev2 + nums[i]). Update.

Time: O(n) | Space: O(1)

Solutions

C

int rob(int* nums, int n) {
    int prev2=0,prev1=0,curr;
    for(int i=0;i<n;i++){curr=prev1>prev2+nums[i]?prev1:prev2+nums[i];prev2=prev1;prev1=curr;}
    return prev1;
}

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2=0,prev1=0;
        for(int n:nums){int curr=max(prev1,prev2+n);prev2=prev1;prev1=curr;}
        return prev1;
    }
};

Java

class Solution {
    public int rob(int[] nums) {
        int prev2=0,prev1=0;
        for(int n:nums){int curr=Math.max(prev1,prev2+n);prev2=prev1;prev1=curr;}
        return prev1;
    }
}

JavaScript

var rob = function(nums) {
    let [prev2,prev1]=[0,0];
    for(const n of nums){const curr=Math.max(prev1,prev2+n);prev2=prev1;prev1=curr;}
    return prev1;
};

Python

class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2=prev1=0
        for n in nums:
            prev2,prev1=prev1,max(prev1,prev2+n)
        return prev1

Complexity

Time: O(n) | Space: O(1)