House Robber Problem

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;
}