House Robber Problem
Application of Decision Making Approach of Dynamic Programming

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
Problem Statement:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you 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 nonnegative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
Solution:
This is a direct use of Dynamic Programming: Decision Making Approach. For every house we have two choices:
either rob the house,
In this case after robbing the house we need to see how much we will get by not robbing the house next to it. 
or, do not rob the house.
In this case we have two choices: (1) either rob the next house, or (2) do not rob the next house. Both the choices follow the given condition in the given problem. So we would choose the one that gives us maximum value.
Recurrence Relation:
dp[i][0] indicates maximum amount of money that can be robbed if robber did not rob i^{th} house, considering houses [0...i]
dp[i][1] indicates maximum amount of money that can be robbed if robber did rob i^{th} house, considering houses [0...i]
money[i] indicates amount of money stashed at i^{th} house
Total number of houses = n and they are numbered from 0 to (n  1)
dp[i][1] = dp[i  1][0] + money[i]
dp[i][0] = Math.max(dp[i  1][1], dp[i  1][0])
base condition: dp[0][0] = 0 if the robber does not rob the first house he/she has no money with him/her, considering houses [0...0]
base condition: dp[0][1] = money[0] if the robber rob the first house he/she has no money with him/her, considering houses [0...0]
Java Code:
This is a Premium Content.
Please subscribe to Algorithms course to access the solution.
Python Code:
This is a Premium Content.
Please subscribe to Algorithms course to access the solution.
Further Optimization:
If you look closely at the above solution you would notice that there is still room for space optimization. Look for every house i we need DP result for house (i  1). So instead of keeping an array to keep DP result for all houses, we could have just kept two variables to store the result of the previous house for all house i for all i = 0 to (n  1).
Look closely at the below implementation to see how we can transform a DP solution that shows sign of further space optimization into a more space optimized solution. Try to have a strong grasp on this simple example. This will help you to identify and perform space optimization in several complex Dynamic Programming problems in future. We will look at such kind of optimization throughout our Dynamic Programming series.
Java Code:
This is a Premium Content.
Please subscribe to Algorithms course to access the solution.
Python Code:
This is a Premium Content.
Please subscribe to Algorithms course to access the solution.
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn