House Robber (DP-12)

A professional robber is planning to rob houses along a street. Each house has a certain amount of money stashed in them. You need to find out the maximum amount of money that the robber can steal with the constraint that the robber cannot rob adjacent houses.
You are given an array of non-negative integers which the represents the amount of money in each house and you need to determine the maximum amount of money that can be stolen.

Sample Input: Arr = {6, 7, 1, 3, 8, 2, 4};
Expected Output: 19.
Explanation: The robber can steal from houses with money {6, 1, 8, 4} to obtain a total amount of 19 without violating the constraint.

Algorithm:

  1. The above problem has optimal substructure and overlapping sub-problems and hence can be solved using Dynamic programming.
  2. We use bottom up approach to solve the problem. We create an array DP of size (n) to store the results of the sub-problems. DP [i] stores the result for houses from [0 … i]. DP [0] is equal to Arr [0] because is there is only 1 house, the maximum stolen amount will be equal to the money in that house. DP [1] is equal to maximum of Arr[0] and Arr[1].
  3. We iterate for remaining values, in each iteration we do the following –
    For each house we have two choices – Either we can skip the house or we can take the money from the current house and skip the previous house.
#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> arr){
	int n = arr.size();
	if(n==0){
		return 0;
	}
	if(n==1){
		return arr[0];
	}
	if(n==2){
		return max(arr[0], arr[1]);
	}
	vector<int> dp(n);
	dp[0]=arr[0];
	dp[1]=max(arr[0], arr[1]);
	for(int i=2; i<n; i++){
		dp[i]=max(arr[i]+dp[i-2], dp[i-1]);
	}
	return dp[n-1];
}

int main(){
	vector<int> nums = {6, 7, 1, 3, 8, 2, 4}; 
	cout<<helper(nums);
	return 0;
}

Also, check out another popular interview question Minimum Edit Distance.

3 comments

Leave a Reply

Your email address will not be published.