Breaking Down the House Robber Problem (Step-by-Step)

The "House Robber" problem is one of the most classic introductions to Dynamic Programming (DP). It teaches you the fundamental concept of "Choice" in algorithms: at every step, you have two options, and your decision affects the future.

In this post, I will walk you through the thought process, starting from a basic DP solution and then optimizing it to use constant O(1) space.

The Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. However, there is one constraint:

Adjacent houses have security systems connected. If you rob two adjacent houses on the same night, the alarm will trigger.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

The Intuition: The Choice

At every single house i, you have exactly two choices:

• Option A (Rob this house): If you rob house i, you get nums[i] money. But, you CANNOT rob house i-1. This means your previous loot must have come from house i-2.
  Total = nums[i] + loot from (i-2)
• Option B (Skip this house): If you skip house i, you don't get any money from here. But, you keep whatever maximum loot you had at house i-1.
  Total = loot from (i-1)

We simply take the maximum of these two options at every step.

Approach 1: Dynamic Programming Array

We can create a dp array where dp[i] represents the maximum money we can steal up to house i. Space: O(N)

class Solution {
public:
    int rob(vector<int>& nums) {
       if(nums.size() == 1) {
           return nums[0];
       }

       int n = nums.size();
       vector<int> dp(n, 0);

       // Base cases
       dp[0] = nums[0];
       dp[1] = max(nums[0], nums[1]);

       // Fill the DP table
       for(int i = 2; i < n; i++) {
           // Decision: Max of (Skipping current, Robbing current + prev-prev)
           dp[i] = max(dp[i-1], nums[i] + dp[i-2]);
       }

       return dp[n-1];
    }
};

Approach 2: Space Optimization

If you look closely at the code above, to calculate dp[i], we only need dp[i-1] and dp[i-2]. We don't need the entire array!

We can replace the array with just two variables: prev_rob (representing i-2) and max_rob (representing i-1). This reduces our space complexity significantly. Space: O(1)

class Solution {
public:
    int rob(vector<int>& nums) {
       int prev_rob = 0;
       int max_rob = 0;

       for(int i = 0; i < nums.size(); i++) {
            // temp represents the max loot if we include current house
            int temp = max(max_rob, prev_rob + nums[i]);

            // Shift our variables forward
            prev_rob = max_rob;
            max_rob = temp;
       }

       return max_rob;
    }
};

Dry Run of O(1) Code

Let's say nums = [1, 2, 3, 1]

• i=0 (House val 1): temp = max(0, 0+1) = 1. prev becomes 0, max becomes 1.
• i=1 (House val 2): temp = max(1, 0+2) = 2. prev becomes 1, max becomes 2.
• i=2 (House val 3): temp = max(2, 1+3) = 4. prev becomes 2, max becomes 4.
• i=3 (House val 1): temp = max(4, 2+1) = 4. prev becomes 4, max becomes 4.

Final Answer: 4.

Conclusion

This optimization from O(N) space to O(1) space is a very common pattern in interview questions. Whenever you see a DP problem where you only look back `k` steps, you can usually optimize it to O(k) space using variables or a sliding window.