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.
Algorithm:
The problem can be cut down to sub-problem of finding whether to rob from ith house or not.
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,
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:
Example with explanation:
That gives the maximum amount that can be robbed without breaking the security.
C++ Implementation:
Output