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 (n1)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;
}
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 (n1)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;
}
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 n1 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: Bottomup Approach
In recursion and the above dp approach, we were passing the problem and solving it in the future. But in the bottomup 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[i1] + dp[i2]
 if we don't rob this house, then the maximum profit would be dp[i1].
 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[i1]+dp[i2]. (weâ€™re doing nums[i1] as the indexing in the money vector is 0 based, and weâ€™re looping here for onebased).
 Option 2: donâ€™t rob the ith house. The maximum profit will be dp[i1].
 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[i1],money[i1]+dp[i2]); // 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;
}
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[i1] and dp[i2]onebased. So, instead of using dp we can use two variables, prev(which is basically dp[i1]) and second_prev(which is basically dp[i2]).
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[i1]+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[i1]+second_prev. (weâ€™re doing nums[i1] 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[i1]+second_prev,prev); // The answer for current i
// will be max(money[i1]+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;
}
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 onestop 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 productbased 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!