A professional robber is planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping him from robbing each of them is that adjacent houses have security system connected

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-04-30

249

House Robber

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

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money he can rob tonight without alerting the police.

Solution

Example

Input: [1,2,3,1]
Output: 4
Explanation:
Option 1:
Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount he can rob = 1 + 3 = 4.
Option 2:
Rob house 2 (money = 2) and then rob house 4 (money = 1).
             Total amount he can rob = 2 + 1 = 3
So, option 1 maximizes the money stolen.

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-04-30

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

The problem can be cut down to sub-problem of finding whether to rob from ith house or not.

Let f(i)=amount of money stolen after robbing house i

Now, in case of taking decision whether to rob from ith house or not, it completely depends on where the money maximizes. Since, adjacent houses are connected, the robber can't rob two adjacent house. Either he can rob from (i-1)th house or he can rob from ith house after robbing from (i-2)th house. To maximize the money simply find which results in maximum amount. In terms of recursive relation we can write,

f(i)=maximum(f(i-2)+money of ith house,f(i-1))

This recursive relation ultimately yields to the maximum amount that can be robbed.

We can form our DP matrix and convert the recursive relation in memorization.

Pre-requisite:

A 1D array where mone stashed in houses are stored. Let the array to be money

Steps:

1.  Bases case:
    IF (n==0)
        Return 0;
    IF (n==1)
        Return money[0];
2.  Initialize DP matrix
    int house[n]; // DP matrix
    //initialize all elements with their respective money
    for(int i=0;i<n;i++) 
        house[i]=money[i];

3.  IF there is only one house, then simply rob the money.
        house[0]=money[0];

4.  IF there is two house rob from the house having maximum amount
    house[1]=(money[0]>money[1])?money[0]:money[1];
5.  Formulate the recursive function:
    for(int i=2;i<n;i++){ //for more houses
        house[i]=max(house[i]+house[i-2],house[i-1]);
    }
    //house[i-2]= f(i-2) // as updated by DP matrix
    // house[i-2]= f(i-2) // as updated by DP matrix
    // house[i]( on R.H.S) = money of ith house // as not still updated by DP matrix
    // house[i] (on L.H.S) = f(i) // as it's going to be updated by DP matrix

6.  Return house[n-1]

Example with explanation:

Let's solve an example using the algorithm:

No of houses: 6
Money stashed at houses:
4, 2, 2, 10, 4, 2

Initially DP matrix
4 (0th) | 2 (1st) | 2(2nd) | 10 (3rd) | 4 (4th) | 2 (5th)

After step -3 & step - 4:
4 (0th) | 4 (1st) | 2(2nd) | 10 (3rd) | 4 (4th) | 2(5th)

At step-5:
House index starts from 0

Iteration 0:
house[2]=max(house[2]+house[0],house[1]);
house[2]=6 // house[2]+house[0]=6 &house[1]=4
that means rob at house 0 & then at house 2
4 (0th) | 4 (1st) | 6(2nd) | 10 (3rd) | 4 (4th) | 2 (5th)

Iteration 1:
house[3]=max(house[3]+house[1],house[2]);
house[3]=14 // house[3]+house[1]=14&house[2]=6
that means rob at house 1 & then at house 3 (decision changed)
4 (0th) | 4 (1st) |	6(2nd) | 14 (3rd) |	4 (4th) | 2 (5th)

Iteration 2:
house[4]=max(house[4]+house[2],house[3]);
house[4]=14 // house[4]+house[2]=10&house[3]=14
that means rob at house 1& then at house 3 (no change in last decision)
4 (0th) | 4 (1st) |	6(2nd) | 14 (3rd) |	10 (4th) | 2 (5th)

Iteration 3:
house[5]=max(house[5]+house[3],house[4]);
house[5]=16 // house[5]+house[3]=16&house[4]=10
that means rob at house 1 & then at house 3 & then at house 5(final)
4 (0th) | 4 (1st) |	6(2nd) | 14 (3rd) |	10 (4th) | 16 (5th)

That gives the maximum amount that can be robbed without breaking the security.

C++ Implementation:

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

int max(int x,int y) {return (x>y)? x:y;} 

int rob(vector<int>& money) {
	int n=money.size();
	//base cases
	if(n==0)
		return 0;
	if(n==1)
		return money[0];

	int house[n];

	//initialize DP matrix
	for(int i=0;i<n;i++)
		house[i]=money[i];
	house[0]=money[0];
	house[1]=(money[0]>money[1])?money[0]:money[1];

	//Evaluate the recursive formula 
	for(int i=2;i<n;i++){
		house[i]=max(house[i]+house[i-2],house[i-1]);
	}
	//return max amount can be robbed
	return house[n-1];
}

int main(){
	int n,m;
	cout<<"enter no of houses\n";
	cin>>n;

	vector<int> money;

	cout<<"enter respective money's of houses\n";
	for(int i=0;i<n;i++){
		cin>>m;
		money.push_back(m);		
	}

	cout<<"maximum amount that can be robbed: "<<rob(money)<<endl;

	return 0;
	
}

Output

First run:
enter no of houses
4
enter respective money's of houses
1 2 3 1
maximum amount that can be robbed: 4

Second run:
enter no of houses
6
enter respective money's of houses
4 2 2 10 4 2
maximum amount that can be robbed: 16

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)