[LeetCode] 198. House Robber

 

198. 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 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.

 

My Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        elif len(nums)==1:
            return nums[0]

        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-2]+nums[i], dp[i-1])

        return dp[len(nums)-1]

 

Improved

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        elif len(nums)==1:
            return nums[0]

        prev2=prev1=0

        for i in nums:
            current = max(prev1, prev2+i)
            prev2=prev1
            prev1=current

        return current

 

 

1. Breaking the Proble into Subproblems

Constraints

- If you rob a house, you can't rob its adjacent houses.

- To calculate the maximum money that can be robbed up to a certain house, you need the results of previous calculations.

Optimal Substructure

- Let dp[i] represent the maximum money that can be robbed from the first house up to the i-th house

- There are two scenarios for house i:

  Skip robbing house i: dp[i-1]

  Rob house i: nums[i] + dp[u-2]

- Hence, the recurrenc relation is:

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

 

 

2. Base Case Initialization

- dp[0] = nums[0] : The maximum money robbed from the first house is the value of that house

- dp[1] = max(nums[0], nums[1]): The maximum money robbed from the first two houses is the larger of the two values.

 

3. Recurrence Relation Iteration.

- Using the recurrence relation above, compute dp[i] for i=2 to n-1. The final result will be stored in dp[n-1], which represents the maximum money that can be robbed from all houses.

 

4. Space Optimization

Instead of using an entire dp array, only the last two computed values are needed at any point Thus, we can optimize space complexity by using two variables:

- prev1 : Represents dp[i-1]

- prev2 : Represents dp[i-2]

 

Update these variables iteratively:

  curr = max(prev1, nums[i] + prev2)

Then, set:

  prev2 = prev1, prev1 = curr