Data Structures & Algorithms in Java – Dynamic Programming – House Robber

Problem:

A robber goes to rob in a series of houses built next to each other. He can’t rob from two consecutive houses , this will trigger an alarm. How much maximum money can he steal ?

Input:

The array [1,2,3,1] represents money in each house starting from the first index.

Output:

Maximum amount the robber can steal without stealing in consecutive houses is 1 + 3 = 4

For the input [2,1,1,2] , the maximum money the robber can steal is 2 + 2 = 4

Try out the solution here:

https://leetcode.com/problems/house-robber/

Solution:

Hint:

• Use dynamic programming – as you iterate the array , store the maximum the robber steal until that house in an array

ALGORITHM:

STEP1: Initialize an array which will hold the maximum money the robber can steal until that house

STEP2: For the first house , store the value of the money in that house

STEP3: If there is more than one house , store the maximum of the money in house 1 and house 2 in the second position of the output array because the robber can steal either from house 1 or house 2 but not both since they are next to each other

STEP4: For the rest of the houses , compare the maximum money that could be stolen until the previous house (stored in the output array already) and the sum of the maximum money that could be stolen until the previous to previous house and the money in the current house.

STEP5: Return the money in the last element in the output array.

The basic logic here is :

Max money until a house = Max of ( Max money until the previous house , Max money until previous to previous house + money in current house)

Code:

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

We can avoid the code:

if(nums.length > 1){
dp[1] = Math.max(nums[0],nums[1]);
}

if we start storing the output in the output array from index 1.

That is 0th element in the input is represented by 1st element in the output and so on.

The refactored code :

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

Time complexity is O(n) as you make a single pass through the array.

Space complexity is O(n) for the output array.

That’s it!