Problem 198

(Last updated: )

Question 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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Solution

After yesterday’s problem, this feels like a breath of fresh air. This is a simple 1-d DP

Main idea:

Create a 1-d dp array with the intention that dp[i] stores the maximum robbable amount given that we rob house i. Certainly the starting state is dp[0]=nums[0] and dp[1] = max(nums[0],nums[1]). Now to get dp[i] simply do

dp[i] = nums[i] + max(dp[:i-1])

Note 1: If the optimal approach is to not rob house i, then that will be factored in a future scenario where the house currently being robbed is an optimal house to rob.

We can also further optimize this by realizing that suppose we are at house i, which we are forced to rob. Then it suffices to only consider dp[i-2] and dp[i-3] for our max function. This is because, by design our dp array is increasing, and so the earlier terms will not be the maximum. The latest maximum entry will be in dp[i-2] if we chose to rob house i-2. The only reason to not rob house i-2, would be that we had already robbed house i-3, which means our maximum profit is stored in dp[i-3].

Code:

1
2
3
4
5
6
7
8
9
10
11
12
def rob(self, nums: List[int]) -> int:
    if(len(nums) <=2):
        return max(nums)
    
    num_houses = len(nums)
    dp = [0 for _ in range(num_houses)]
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, num_houses):
        dp[i]=nums[i]+max(dp[i-2], dp[i-3])
    return max(dp)

Comments:

Time complexity: O(n)

At the time of submission, the above solution passes leetcode submission cases in 27ms, beats 98.25% of users. It uses 16.53MB of memory, beating 57.82% of users.