🙏

জয়  শ্রী  রাম

🕉

---

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]

Java Code:

class Robber {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;    
        }
        
        int n = nums.length;
        int[][] dp = new int[n][2]; 
        
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][1] = dp[i - 1][0] + nums[i];
            dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}

Python Code:

class Solution(object):
    def rob(self, nums):
        if len(nums) == 0:
            return 0
        n = len(nums)
        dp = [[0 for j in range(2)] for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = nums[0]
        i = 1
        while i < n:
            dp[i][1] = dp[i - 1][0] + nums[i]
            dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
            i += 1
        return max(dp[n - 1][0], dp[n - 1][1])

Further Space Optimization (2D Array to 1D Array):

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int[] memo = new int[len];
        memo[len - 1] = nums[len - 1];
        memo[len - 2] = Math.max(nums[len - 2], nums[len - 1]);
        for (int i = len - 3; i >= 0; i--) {
            memo[i] = Math.max(
                nums[i] + memo[i + 2], // include current house
                memo[i + 1] // don't include current house
            );
        } 
        return memo[0];
    }
}
    

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:

Login to Access Content

Python Code:

Login to Access Content

Instructor: