Back to solutions

House Robber

MediumDynamic Programming

Maximize the loot from houses in a row where robbing two adjacent houses triggers the alarm.

Open problem
Constraints
  • 1 <= n <= 100
  • 0 <= nums[i] <= 400

Rolling DP of take vs skip

Time O(n)Space O(1)

At each house the best total is the larger of skipping it (previous best) or robbing it (best two houses back plus current). Track those two rolling values.

#include <bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int x : nums) {
        int next = max(curr, prev + x);
        prev = curr;
        curr = next;
    }
    return curr;
}