House Robber — LeetCode 198

What does it ask?

You are a robber on a street of n houses. Each house has some money. You cannot rob two adjacent houses — the alarm triggers.

Return the maximum amount you can rob without triggering any alarm.

The key realization: at every house you face exactly one choice — rob it (skip the previous) or skip it (keep whatever the previous best was).

Recurrence relation

// dp[i] = max money robbing up to house i

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

for i = 2 to n−1:
  rob = dp[i−2] + nums[i]
  skip = dp[i−1]
  dp[i] = max(rob, skip)

return dp[n−1]

💡 Key insight: dp[i−2] + nums[i] means "rob this house plus the best from two steps back." dp[i−1] means "skip this house, keep the best so far." We only ever need the last two values — which is why the optimized solution uses just two variables prev2 and prev1, giving O(1) space.

Decision at each house i ≥ 2

Option A — Rob house i

dp[i] = dp[i−2] + nums[i]
Skip i−1 (adjacent), add this house's money to best from two back

Option B — Skip house i

dp[i] = dp[i−1]
Don't rob, just carry forward the best result from previous house

Final decision

dp[i] = max(A, B)
Whichever gives more money — greedy would fail here, DP is correct

Space optimized

prev2, prev1 → cur
Only two variables needed — dp array is for clarity only

Complexity

Time

O(n)

Single left-to-right pass through all n houses.

Space (DP array)

O(n)

Storing dp[0..n−1]. Can be reduced to O(1) with two variables.

Space (optimized)

O(1)

Track only prev2 and prev1 — shown live in the animation.

Examples & edge cases

Live Animation — House Robber DP

Unvisited house Current house i dp filled Final answer dp[i−1] (skip ref) dp[i−2] (rob ref)

⏸ Waiting to start

dp[ ] array — max money robbing houses 0 through i

prev2 = dp[i−2]

—

rob reference

prev1 = dp[i−1]

—

skip reference

nums[i] (current)

—

house value

🔓 Rob house i

prev2 + nums[i] = —

🚶 Skip house i

prev1 = —

✅ Best choice

dp[i] = —

Robbed

—

houses chosen

Skipped

—

houses

Current dp[i]

—

Answer

—

Step — of —

Select an example and press Play to begin.

🏆 Max loot: —

Speed Medium

Step-by-step DP table

Step	House i	nums[i]	Rob (dp[i−2]+val)	Skip (dp[i−1])	dp[i]	Decision

C++ implementation (both versions)

house_robber.cpp · LeetCode 198

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

class Solution {
public:
    // ── Version 1: DP array O(n) space ──
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            int rob_it  = dp[i-2] + nums[i]; // rob this house
            int skip_it = dp[i-1];           // skip this house
            dp[i] = max(rob_it, skip_it);
        }

        return dp[n-1];
    }

    // ── Version 2: Optimized O(1) space ──
    int robOptimized(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            int cur = max(prev2 + nums[i], prev1);
            prev2 = prev1;  // slide window forward
            prev1 = cur;
        }

        return prev1;
    }
};

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars