2 minute read

198. House Robber

Difficulty: Medium

Related Topics: Array, Dynamic Programming

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.

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.

First Attempt:

Code:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return max(nums)
        house = [0 for i in range(len(nums))]
        curr = 3
        house[0] = nums[0]
        house[1] = nums[1]
        house[2] = nums[2]+nums[0]
        while curr < len(nums):
            house[curr] = nums[curr] + max(house[curr-2], house[curr-3])
            curr+=1
            print(curr, house)
        return max(house)

Feedbacks:

If there are less than or equal to 2 houses, I simply return the max value of the list. Else, I create a new empty list. And for each index, I store the maximum money that I can rob. To do this, I have to compare house located at -2 index and -3 index from current index and add maximum money that I can rob to money in current house. It solved the problem, but I think I can more optimize this code.

Suggested Solution:

Code:

class Solution:
    def rob(self, nums: List[int]) -> int:
        # edge cases:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        if len(nums) == 2: return max(nums)
        
        # dynamic programming - decide each problem by its sub-problems:
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], nums[i]+dp[i-2])
        
        return dp[-1]

Feedbacks:

First, work on the base cases first. If there are more than 2 houses, I create a dp list. For each index, I store the maximum amount of money that I could rob till that house. For example, at third house, I can choose whether I don’t rob third house or I rob third house. This can be determined by comparing money I could rob till house 2 and money at third house and first house, since I cannot rob any two adjacent houses.

You may also enjoy