Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1: Recursion
3.1.
C++ Implementation
3.2.
Complexities
4.
Approach 2: Dynamic Programming
4.1.
C++ Implementation
4.2.
Complexities
5.
Approach 3: Bottom-up Approach
5.1.
C++ Implementation
5.2.
Complexities
6.
Approach 4: Using Constant Space 
6.1.
C++ Implementation
6.2.
Complexities
7.
Frequently Asked Questions
7.1.
What is dynamic programming, and where is it used?
7.2.
What are overlapping subproblems?
7.3.
What is an optimal substructure?
7.4.
Is dynamic programming used in real life?
7.5.
Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

House Robber

Author Shreya Deep
2 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

House robbery is something that happens quite a lot. When robbers do their robbing, they always want to make sure not to get caught. If someone gives you the list of houses in which the robbers are robbing along with their amount of money present, you can find the total profit one can make out of it. This is simple. 

But the problem comes when you’re given a list of houses which robbers can rob. Additionally, there is some restriction on the way through you will choose to rob. Then, to find the maximum profit, you’ll have to do some serious calculations. 

In this article, we’ll learn about the techniques to get the maximum profit in this situation. So without any further ado, let’s get started! 

(Also, see Data Structures)

Problem Statement

You are given the amount of money present in n houses you can rob in a vector “money.” But there is a restriction on the method of robbing. The restriction 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. Therefore, you’ll always have to avoid robbing in two continuous houses. 

Your task is to calculate the maximum amount of money you can rob without alerting the police. 

Examples: 

INPUT : money = [1,2,3,1]

OUTPUT:  4

example 1

By robbing house 1 (money=1) and then house 3 (money=3), you’ll have the maximum amount of money = 4. There is no other way to rob more than this amount of money.

INPUT : money=[2,7,9,3,1]

OUTPUT:  12

example 2

By robbing house 1 (money=2), then house 3 (money=9), and then house 5 (money=1), you’ll have the maximum amount of money = 12. There is no other way to rob more than this amount of money.

Recommended: Please try it on “Coding Ninjas Studio” before moving on to the solution approach.

Approach 1: Recursion

(See Recursion)

The restriction is that a robber can’t rob two adjacent houses. 

So, let’s say we’re indexing from 0, and you’re in the front of the 0th house. Here, you’ve got two choices. Either you can take whatever is in house 0 and go to house 2 (Note that now you cannot move to house one now) OR you leave house 0 and rob house 1. We’ll take the maximum of these two choices. 

Thus we solve the problem recursively (where the function “maxProfit” returns the maximum profit from ith house to (n-1)th house)  with the above two choices, and whenever we reach the end, i.e., index >= n simply return 0. We’re returning 0 when we’ve reached the end because we know we can’t make any additional money as there are no additional houses left.

So, for the ith index:

  • Option1 (rob the house): Rob the current house at index i and move to index i+2. The profit will be money[i]+maxProfit(money, i+2). 
  • Option2 (rob the next house): rob the next house at index i+1 and see the profit. The profit will be maxProfit(money,i+1). 

Base cases:

  • If the i>=n, that means we’ve already reached the end of the houses, and there are no other houses left. So just return 0. 

Steps are:

  • Input the number of houses
  • Declare vector money for storing the amount of money in each house and input values in it.
  • Call the rob function with money as the only parameter. 
  • In the rob function:
    • Call the maxProfit function with index 0 as in the beginning; we’ll be starting from 0th house only.
    • In the maxProfit function, 
      • First, check if there are no houses left. If no houses are left, return 0.
      • Then calculate the answers for the two choices. 
        • Option 1: Rob the current house at index i and move to index i+2. The profit will be money[i]+maxProfit(money, i+2).
        • Option 2: rob the next house at index i+1 and see what the profit is. The profit will be maxProfit(money,i+1).
      • Return the maximum of both options.
    • Return the value returned by the maxProfit function.
  • Print the answer returned from the rob function.

C++ Implementation

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

int maxProfit(vector<int>&money,int index){
    if(index>=money.size()){ // Check if there are no houses left. If no houses left, return 0.
        return 0;
    }
    int op1 = money[index]+maxProfit(money,index+2); // Option 1 -> rob the current house and go on 
    //to the (index+2)th house 
    int op2 = maxProfit(money,index+1); //Option 2-> Don't rob the current house and go on to the next one.
    int mx = max(op1,op2); // Return the maximum of these two options.
    return mx;
}

int rob(vector<int>&money){
    return maxProfit(money,0); // Call the maxProfit function with index 0 
    //as in the beginning, we'll starting from 0th house only.
}

int main(){
    int n;
    cin>>n; //Input the number of houses
    vector<int>money(n); // vector for storing the amount of money in each house
    for(int i=0;i<n;i++){
        cin>>money[i]; 
    }
    int ans = rob(money); // Call the rob function.
    cout<<ans<<endl;
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

[2,7,9,3,1]

Output

12

Complexities

Time complexity

O(2^n), where n is the number of houses.

Reason: In the worst case, for each index i, we are making two recursion calls for each i. Thus, the complexity will be exponential and equal to O(2^n).

Space complexity

O(n), where n is the length of the string.

Reason: In the worst case, the extra space used by the recursion stack can go up to a  maximum depth of n. Hence the space complexity is O(n).

Approach 2: Dynamic Programming

The above approach took a lot of execution time because we call the function “maxProfit” for one index more than once. So we can optimize it, and the best way to optimize it will be using dynamic programming to remember the answers for indexes that we already calculated. 

The new things we do here is just that we store the answers return by maxProfit in a vector dp, where dp[i] denotes the maximum profit robber can get from ith house to (n-1)th house. Every time there is the function call for maxProfit at index i, we check if we’ve already calculated the value of dp[i]. 

Steps are:

  • Input the number of houses
  • Declare vector money for storing the amount of money in each house and input values in it.
  • Call the rob function with money as the only parameter. 
  • In the rob function:
    • declare the vector dp of size n and initialize all the values to -1.
    • Call the maxProfit function with index 0 as in the beginning; we’ll be starting from 0th house only. Also, pass the dp vector in the maxProfit function by reference.
    • In the maxProfit function, 
      • First, write the base case. Check if there are no houses left. If no houses are left, return 0.
      • If it’s not the base case, check if the answer is already calculated, i.e., if dp[i]!=-1. If yes, return the value of dp[i] already. If not, move forward to the next steps.
      • Then calculate the answers for the two choices. 
        • Option 1: Rob the current house at index i and move to index i+2. The profit will be money[i]+maxProfit(money, i+2).
        • Option 2: rob the next house at index i+1 and see what the profit is. The profit will be maxProfit(money,i+1).
      • Return the maximum of both options and update dp[i] to the maximum of both options (memoization).
    • Return the value returned by the maxProfit function.
  • Print the answer returned from the rob function.

C++ Implementation

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

int maxProfit(vector<int>&money,int index,vector<int>&dp){
    if(index>=money.size()){ // Check if there are no houses left. If no houses left, return 0.
        return 0;
    }
    if(dp[index]!=-1){ //Check if the answer for this index is already calculated. 
        //If yes, return the answer.
        return dp[index];
    }
    int op1 = money[index]+maxProfit(money,index+2,dp); // Option 1 -> rob the current house and go on 
    //to the (index+2)th house 
    int op2 = maxProfit(money,index+1,dp); //Option 2-> Don't rob the current house and go on to the next one.
    int mx = max(op1,op2); // Return the maximum of these two options.
    dp[index] = mx; //Update the value of dp[index] for the current index.
    return mx;
}

int rob(vector<int>&money){
    vector<int>dp(money.size(),-1); // Declare and initialie the dp vector
    return maxProfit(money,0,dp); // Call the maxProfit function with index 0 
    //as in the beginning, we'll starting from 0th house only.
}

int main(){
    int n;
    cin>>n; //Input the number of houses
    vector<int>money(n); // vector for storing the amount of money in each house
    for(int i=0;i<n;i++){
        cin>>money[i]; 
    }
    int ans = rob(money); // Call the rob function.
    cout<<ans<<endl;
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

[2,7,9,3,1]

Output

12

Complexities

Time complexity

O(n), where n is the number of houses.

Reason: Apparently, we’re only calculating the answer for each index from i=0 to n-1 once only. Thus the time complexity will be linear and equal to O(n).

Space complexity

O(n), where n is the number of houses.

Reason: Space taken here is by the dp vector of size equal to the number of houses. Thus space complexity is O(n).

Approach 3: Bottom-up Approach

In recursion and the above dp approach, we were passing the problem and solving it in the future. But in the bottom-up dp we move forward by solving small subproblems to get to the result. Now we make one dp array of length (n+1 ). Here, dp[i] represents the maximum profit robber can get with i houses

  • We know that when there are 0 houses, then the maximum money robber can make is 0.  So dp[0]=0. 
  • dp[1]= nums[0] (Since if there is only one house, this is the maximum profit robber could get). 
  • Now we apply the for loop, which starts from i=2 and goes to i<=n. In this for loop, for each i, there are two possibilities.
    • If we rob the ith house, then the maximum profit would be nums[i-1] + dp[i-2]
    • if we don't rob this house, then the maximum profit would be dp[i-1].
    • So we take the maximum of these two options, update dp[i] to it, and move on to the following i.

Steps are:

  • Input the number of houses
  • Declare vector money for storing the amount of money in each house and input values in it.
  • Call the rob function with money as the only parameter. 
  • In the rob function:
    • Check if the number of houses is 0. If yes, the maximum profit we can make is 0. Thus return 0.
    • Otherwise, declare and initialize the dp vector of size (n+1) to 0.
    • Write the base cases we discussed above. dp[0]=0 and dp[1] = money[0].
    • Run a for loop from i=2 to i<=n. For each i,
      • Option 1: rob the ith house. The maximum profit will be money[i-1]+dp[i-2]. (we’re doing nums[i-1] as the indexing in the money vector is 0 based, and we’re looping here for one-based). 
      • Option 2: don’t rob the ith house. The maximum profit will be dp[i-1]. 
      • Update the value of dp[i] to the maximum of these two values.
    • Return dp[n] as there are total of n houses. 
  • Print the answer returned from the rob function.

C++ Implementation

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

int rob(vector<int>&money) {
    if(money.size()==0) // If there are no houses, answer should be 0. So return it.
        return 0;
    int n = money.size();
    vector<int> dp(n+1,0); // Declare and initialise the vector dp of size n+1 to 0.
    // Base cases
    dp[0]=0; 
    dp[1]=money[0];
    for(int i=2;i<=n;i++){ // Calculate the answer for each i from i=2 to i<=n.
        dp[i]=max(dp[i-1],money[i-1]+dp[i-2]); // Take the max of the two choices 
        //and update the dp[i] value to it.
    }
    return dp[n]; // Return dp[n] 
}

int main(){
    int n;
    cin>>n; //Input the number of houses
    vector<int>money(n); // vector for storing the amount of money in each house
    for(int i=0;i<n;i++){
        cin>>money[i]; 
    }
    int ans = rob(money); // Call the rob function.
    cout<<ans<<endl;
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

[2,7,9,3,1]

Output

12

Complexities

Time complexity

O(n), where n is the number of houses.

Reason: we’re only calculating the answer for each index from i=0 to n once only. Thus the complexity will be linear and equal to O(n).

Space complexity

O(n), where n is the number of houses.

Reason: Space taken here is by the dp vector of size equal to the number of houses. Thus space complexity is O(n).

Approach 4: Using Constant Space 

Now we can reduce the space complexity of O(n) further to O(1) by observing that we actually need the information of only two previous states i.e. dp[i-1] and dp[i-2]one-based. So, instead of using dp we can use two variables, prev(which is basically dp[i-1]) and second_prev(which is basically dp[i-2]).

For i=2, we need dp[0] and dp[1]. Thus, initially, second_prev=0 and prev = money[0].

Now, we can calculate the answer for i=2 (say, current) as max(prev, money[i-1]+second_prev). Also, for the further indexes, we’ve to keep updating the second_prev=prev and prev = current.

Steps are:

  • Input the number of houses
  • Declare vector money, for storing the amount of money in each house and input values in it.
  • Call the rob function with money as the only parameter. 
  • In the rob function:
    • Check if the number of houses is 0. If yes, the maximum profit we can make is 0. Thus return 0.
    • Otherwise, initialize two variables, second_prev=0 and prev = money[0].
    • Run a for loop from i=2 to i<=n. For each i,
      • Option 1: rob the ith house. The maximum profit will be money[i-1]+second_prev. (we’re doing nums[i-1] as the indexing in the money vector is 0 based and we’re looping here for 1 based). 
      • Option 2: don’t rob the ith house. The maximum profit will be prev. 
      • The answer for current i will be max of the above two.
      • Update second_prev=prev and prev=current for the further i’s.
    • After we’re out of the loop, return prev as it will contain the answer of the case when i=n.
  • Print the answer returned from the rob function.

C++ Implementation

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

int rob(vector<int>&money) {
    if(money.size()==0) // If there are no houses, answer should be 0. So return it.
        return 0;
    int n = money.size();  
    // Declare and initialize the variables second_prev=0 and prev=money[0]
    int second_prev=0; 
    int prev=money[0];
    // For each index i, calculate the value of maximum.
    for(int i=02;i<=n;i++){
        int current = max(money[i-1]+second_prev,prev); // The answer for current i
        // will be max(money[i-1]+second_prev,prev). 
        // Update the values of second_prev and prev for further i's.
        second_prev = prev;
        prev = current;
    }
    return prev; // Return prev
}

int main(){
    int n;
    cin>>n; //Input the number of houses
    vector<int>money(n); // vector for storing the amount of money in each house
    for(int i=0;i<n;i++){
        cin>>money[i]; 
    }
    int ans = rob(money); // Call the rob function.
    cout<<ans<<endl;
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

[2,7,9,3,1]

Output

12

Complexities

Time complexity

O(n), where n is the number of houses.

Reason: we’re only calculating the answer for each index from i=0 to n once only. Thus the complexity will be linear and equal to O(n).

Space complexity

O(1), where n is the number of houses.

Reason: only space taken here is by the variables which take constant space. Thus space complexity is O(1).

Check out this problem - Count Ways To Reach The Nth Stair 

Frequently Asked Questions

What is dynamic programming, and where is it used?

Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.

What are overlapping subproblems?

A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.

What is an optimal substructure?

A problem is said to have an optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

Is dynamic programming used in real life?

Yes! Dynamic programming is heavily used in computer networks, routing, graph problems, computer vision, artificial intelligence, machine learning,, etc.

Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?

Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.
 

Conclusion

In this article, we discussed the problem - House Robber. One of the efficient solutions to this problem was based on the concept of dynamic programming. This is one of the very interesting and crucial topics, and problems based on this are asked during various coding contests and placements tests.

Recommended Reading:


Recommended Problems:


To practice more such problems, Coding Ninjas Studio is a one-stop destination. You can also Attempt our Online Mock Test Series. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Happy Coding!

Live masterclass