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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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:

1 |
Suppose if you have 0 house, then your amount will be 0. |

1 |
Suppose if you have 1 house, then you rob that house. |

1 |
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.

1 |
[0, 0, 0, 0, 0, 0, 0] |

We leave the 0^{th}index 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.

1 |
[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.

1 2 3 4 5 |
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:

1 2 3 4 5 6 7 |
dp [2] = max [dp 1, dp[0] + num[1]) = max[4, 0 +5] = 5 dp [2] = 5 |

The formula can be generalised as:

1 |
dp[i] = max[dp [i-1], dp[i-2] + num [i – j]] |

## Solution for House Robber Problem in C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#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:

1 |
The profit is = 17 |