• 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.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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 non-negative 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:
  1. 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.
  2. 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 ith house, considering houses [0...i]
dp[i][1] indicates maximum amount of money that can be robbed if robber did rob ith house, considering houses [0...i]
money[i] indicates amount of money stashed at ith 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]



Code:





Please subscribe to access the Full Working Solution.
After subscribing please come back and refresh this page.




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.



Please subscribe to access the Code Optimization.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave