The House Robber Problem

Let’s digest the problem statement 👉 (leetcode link)

Problem Statement :

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Alternative Problem Statement :

Find maximum sum such that no two elements are adjacent

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Noob Thinking :

Oh I see I can’t steal neighboring houses so let me first :

• just steal the 1st house then then 3rd house then the 5th house and so on ..
• OR the 2nd house , then the 4th then 6th and so on …

Now my finally answer would be the max of these two

Ok Noob , Consider this case :

nums = [2,1,1,2]

According to above approach :

Case 1 : 2 + 1 = 3

Case 2: 1 + 2=3

so ans=max(3,3)=3 ( WHICH IS WRONG !!)

Correct output is 4

i.e 2 + 2 ( 1st house and the 4th house )

Clearly we need to consider all the cases . That’s where recursion comes !!

You don't need to do any hard work , let recursion solve the problem for you. Recursion just asks you “ what you want ?”

Start from the 1st house . Now you basically have 2 choices :

• Either don’t steal the current house and go for the next house
• or steal the current house and skip the next house and then go further ( to not alert the police)

Now these 2 choices will cover all our sub problems and we need the max out of the 2 choices . That’s it !! That’s all you need to tell recursion

Recursive code C++

int solve(vector<int> nums,int i)
    {
        if(i>=nums.size()) return 0;
        
        int option1= solve(nums,i+1);  // not stealing current 
        int option2= nums[i] + solve(nums,i+2);  // stealing current 
        
        return max(option1,option2);
    }
    int rob(vector<int>& nums) {
        return solve(nums,0);        // starting from 1st house
    }

Now you know since recursion includes all possible cases. Let us try to make recursive tree to understand this

I have made pair of (Gold, index) . Our sub tree would stop when index≥ size of the array ( because then you can’t access the array OBVIOUSLY)

As you can see at every step we have 2 choices so we make 2 sub trees at every step. Hence time complexity of the recursive code is O(2^N)

So to optimize recursion, we have ….. YES YOU GUESSED IT RIGHT ! DP !!

Let’s memoize this just by adding 2–3 extra lines in the existing code( I have highlighted the extra line to make you realize how easy memoization is )

int solve(vector<int> nums,int i, vector<int> &dp)
    {
        if(i>=nums.size()) return 0;
        
        if(dp[i]!=-1) return dp[i];
        
        int option1= solve(nums,i+1,dp);
        int option2= nums[i] + solve(nums,i+2,dp);
        return dp[i] = max(option1,option2);
    }
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size()+1,-1);
        return solve(nums,0,dp);
    }

By just adding 2 extra lines our code’s time complexity got reduced from O(2^N) to O(N) !!

Actually we are done here but if you want to see the Pure DP i.e without recursion too , I’ll leave it here for you

int rob(int[] nums) {
    vector<int> dp(nums.length()+1);
    dp[0] = 0;
    dp[1] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int val = nums[i];
        dp[i+1] = max(dp[i], dp[i-1] + val);
    }
    return dp[nums.length()];
}

Congrats !! Now you are a DP champ ! ( Just kidding we all need to practice DP a lot xD )

Note: This problem can also be solved without DP

Instead of taking an array for max of previous and current , we can do this using variables !

int rob(vector<int>& nums) {
        
        int temp;
        int incl=nums[0],excl=0;
        
        for(int i=1;i<nums.size();i++)
        {
            temp=max(incl,excl);   // new current max excluding
            incl=excl+nums[i];   // new cuurent max including
            excl=temp;
        }
        return max(incl,excl);
    }

Happy Coding !!