Leetcode — 198. House Robber

The link to the problem: https://leetcode.com/problems/house-robber/

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.

For example, for input nums = [1,2,3,1]
Output is 4.
Since you cannot rob two adjacent houses, the maximum money you can rob is robbing the house 0 and house 2.

Thoughts:

A typical dynamic programming problem. If you have practiced enough problems, you should pop up the idea of using dynamic programming after you read the problem.

The reason why we can use DP is that the maximum money we can earn at the current house depends on the maximum money we can earn in previous houses.

Let dp[i] represents the maximum money we can rob after leaving house i.

We can quickly get a DP formula like —

dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]) if i>=2

We will make a decision on each house from 0 to i. At each house, we will have to make a choice that helps us to earn the most money:

1. Rob this house, and add the amount with the maximum amount we can earn at the house i-2.
2. Don’t rob this house, so the maximum amount we can get is the same as the maximum amount we can earn at the previous house.
   ⚠️The maximum money we earn at house i-1 might or might not including robbing house i.

The reason why we will take the maximum amount at house i-2 when we try to rob house i is that it is possible the maximum amount at house i-1 MIGHT INCLUDE ROBBING THE HOUSE i-1. It is 100% guaranteed that we are following the “not robbing adjacent house” rule if we choose to get dp[i-2].

Below is the 0ms code that beats 99% —

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

Time Complexity and Space Complexity are O(n).

We can also improve the code a little bit by removing the array!

Since we always track the previous two values in the dp array, we can just use two variables to record those numbers.

1. prevTwo — record the maximum amount we can earn at house i-2
2. prevOne — record the maximum amount we can earn at house i-1

And we also need to update those values once we found we can get a new amount at the house i.

Below is the 0ms code that beats 100% —

public int rob(int[] nums) {
        int n = nums.length;
        if(n==0)
            return 0;
        else if(n==1)
            return nums[0];
        
        int prevTwo = nums[0]; // house i-2
        int prevOne = nums[1]; // house i-1
        for(int i=2;i<n;i++)
        {
            int cur = Math.max(prevTwo+nums[i], prevOne);
            prevTwo = Math.max(prevTwo, prevOne);
            prevOne = Math.max(prevOne, cur);
        }
        return Math.max(prevOne,prevTwo);
    }

Time Complexity is still O(n), but space complexity now is O(1).