Approach 1: Brute Force
The task is to determine the greatest amount of sum formed by adding non-consecutive array members. We can use brute force to examine any sequence combination that has non-consecutive components. The indices 1st and Nth, however, are genuinely adjacent. As a result, we must take care not to include both of them in our conclusion. We may independently deduce the highest sum from subarray[1, N – 1] and subarray[2, N]. Both subarrays are now linear. The total of the two subarray-sums will be the outcome.
We can use recursion. In each recursive call, we shall either include or omit the element from our result total. If we select any element at index I, the following index should be I + 2, I + 3, and so on until we reach the last index. Similarly, if we exclude an element at index I, we may use the following recursion on index I + 1 to examine all possibilities that arise from it. In this manner, we examine the options for including and excluding each element. In addition, when we go to each alternate index, all of the items that make up the total will be non-consecutive.
Code
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void combinations(vector <int> &a , int &cur_sum , int idx , int end , int &max_sum_possible)
{
if(idx > end)
return;
cur_sum += a[idx];
if(cur_sum > max_sum_possible)
max_sum_possible = cur_sum;
for(int i = idx + 2 ; i <= end ; i++)
combinations(a , cur_sum , i , end , max_sum_possible);
cur_sum -= a[idx];
combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
return;
}
int rob(vector <int> &houses)
{
int n = houses.size();
if(n == 0)
return 0;
if(n == 1)
return houses[0];
int max_sum = 0 , cur_sum = 0 ;
combinations(houses , cur_sum , 0 , n-2 , max_sum);
combinations(houses , cur_sum , 1 , n-1 , max_sum);
return max_sum;
}
int main()
{
vector <int> a = {2,3,3};
cout << rob(a) << '\n';
}
You can also try this code with Online C++ Compiler
Output:
3
Complexity Analysis
Time Complexity: O(N.2N)
Due to the generation of all possible combinations of robbing houses.
Space Complexity: O(N)
Due to Recursive Stack Frames.
Approach 2: Dynamic Programming
The important thing is that you can't rob both the first and last houses at the same time.
As a result, the key concept is to use dynamic programming. In this section, we will look at two scenarios:
- When you first rob a house,
- When you don't rob the first house, but rather the last.
The dynamic programming approach that must be used with two arrays, given array ARR and new array DP, to store values till the ith house is as follows:
- Set DP[0] to 0 and DP[1] to ARR[1].
- Iterate on the houses.
-
You have two possibilities at the ith house:
- Rob the (i-1)th (prior) home, but skip the ith house, i.e. DP[i-1].
- Rob the ith home after the (i-2)th, skipping the (i-1)th, resulting in DP[i-2] +ARR[i].
- Select the maximum of DP[i-1] and DP[i-2] + ARR[i].
- Return the money you obtained after the last home.
Code
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
Time Complexity: O(N)
Space complexity: O(N)
where 'N' is the length of array.
*/
long long int houseRobberUtil(vector<int> valueInHouse, int start, int end)
{
long long int valueAtIthHouse[valueInHouse.size()];
// Check if the thief may steal the first house or not.
if (start == 0)
{
valueAtIthHouse[0] = valueInHouse[0];
valueAtIthHouse[1] = max(valueInHouse[0], valueInHouse[1]);
}
else
{
valueAtIthHouse[0] = 0;
valueAtIthHouse[1] = valueInHouse[1];
}
for (int i = 2; i < end; i++)
{
valueAtIthHouse[i] = max(valueAtIthHouse[i - 2] + valueInHouse[i], valueAtIthHouse[i - 1]);
}
return valueAtIthHouse[end - 1];
}
int rob(vector <int> &houses)
{
if (houses.size() == 0)
{
return 0;
}
if (houses.size() == 1)
{
return houses[0];
}
return max(houseRobberUtil(houses,0, houses.size() - 1), houseRobberUtil(houses, 1, houses.size()));
}
int main()
{
vector <int> a = {2,3,3};
cout << rob(a) << '\n';
}
You can also try this code with Online C++ Compiler
Output:
3
Complexity Analysis
Time Complexity: O(N)
Because we'll have to go through the full array twice.
Space Complexity: O(N)
Because we'll be making an auxiliary array to keep track of the total amount stolen for each residence.
Soon after this, you can practice one more version of this problem, Loot Houses, which will surely be a cakewalk for you.
Check out Longest Common Substring
Let's wrap up this article and move toward the FAQs section.
Frequently Asked Questions
Why did we consider two cases here?
We considered two cases because, since the first and last house cannot be robbed simultaneously (because the array is circular so they would become adjacent) therefore, we considered two cases, one taking the first house and not the last; another case including the last house and not first.
What is the most optimized approach for the House Robber 2 problem?
The most optimized approach is linear space and time complexity using dynamic programming.
Why did we initialzed dp[0] = 0 ?
We initialized dp[0] = 0 because dp[i] indicated the solution of the problem when we have i number of houses. Since dp[0] indicates solution when we have zero houses, that is why dp[0] is initialized to 0.
Conclusion
Dynamic Programming has always reduced huge time complexities and provided us with the most efficient solution. But note that dynamic programming can only be applied when we can observe some repeated subproblems.
You can study more about Dynamic Programming by visiting Dynamic Programming and Algorithms. If you wish to practice questions based on Dynamic Programming, check out Top Dynamic Programming Questions.
Check out this problem - Minimum Coin Change Problem
I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Also, check out our courses and look at the interview experiences and interview bundle for placement preparations.
Happy Coding!!
24+ registered 
