In this tutorial we shall solve a very famous problem “House Robber” problem. This problem can be solved by using DP method.
Problem Statement:
You are given an array of +ve numbers that represents amount present inside the house, you need to rob the house such that you rob maximum amount. The only condition is that you cannot rob 2 consecutive houses. Robbing 2 consecutive houses will result in alarm and you will get caught.
Let us understand the question:
You are given an array; you need to find the maximum sum of non consecutive elements:
Array [2, 3, 4, 5, 7, 8] Here the sum of 2 non consecutive elements will be 3, 5, 8 = 16. You can also choose: 2, 4, 7 = 13 But the amount is not maximum. You can choose: 4, 7, 8. But this is not valid, because 7, 8 are consecutive.
So to arrive at the solution, you will use dynamic programming approach.
Now we shall understand how to solve the problem:
Suppose if you have 0 house, then your amount will be 0.
Suppose if you have 1 house, then you rob that house.
Suppose if you have 2 house, then you will rob the house that has more money.
Hence by solving in bottom up approach, we can arrive at the solution for getting maximum profit by robbing n houses.
As usual for DP, we create a DP array with once extra size and initialize to 0.
[0, 0, 0, 0, 0, 0, 0]
We leave the 0thindex as 0, because if you don’t have a house, your profit will be ‘0’.
For index 1, we fill the value from index [0] of our given array.
[0, 4, 0, 0, 0, 0, 0]
We did this because, in our DP array, we have considered the possibility if there are no house, then the profit is 0 in index [0] of DP array.
Now we reach index 2. WKT we cannot rob the house at index 2, because we have already robbed 1. But the profit you gain when you rob the house 2 is greater than that of house 1 + all the houses that are robbed before 1.
i.e if you don’t rob house 2, the profit will be house 0 + house 1 = 0 + 4 = 4 but, if you rob house2, the profit will be house 0 _ house 2 = 5
This can be formulated as:
dp [2] = max [dp 1, dp[0] + num[1]) = max[4, 0 +5] = 5 dp [2] = 5
The formula can be generalised as:
dp[i] = max[dp [i-1], dp[i-2] + num [i – j]]
Solution for House Robber Problem in C++
#include<iostream> using namespace std; void houseRobber(int nums[], int length) { if(nums == NULL || length == 0) { cout<<"The profit is = 0"<<endl; return ; } if(length == 1) { cout<<"The profit is = "<<nums[0]<<endl; return ; } int dp[length]; dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for(int i=2; i< length; i++) { dp[i] = max(dp[i-2]+nums[i], dp[i-1]); } cout<<"The profit is = " <<dp[length-1]<<endl; } int main() { int arr[5] = { 3, 8, 4, 8, 9 }; houseRobber(arr, 5); return 0; }
Output:
The profit is = 17
Further Reading: