[LeetCode] 198. House Robber

1. Question

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.

2. Thoughts

1. Use DP
2. Save value of last 3 values.
3. Add only if current + before before is better than before.

3. Tips learned

4. My solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return max(nums)

        first = 0
        second = nums[0]
        third = nums[1]

        for i in range(2, len(nums)):
            temp_third = nums[i] + max(first, second)
            first, second, third = second, third, temp_third

        return max(second, third)

70/70 cases passed (27 ms)
Your runtime beats 98.57 % of python3 submissions
Your memory usage beats 14.42 % of python3 submissions (17.5 MB)

5. AI Solution and Improvements

Your solution to the house robbery problem is on the right track, but there's a more straightforward way to approach it. The problem can be solved using a dynamic programming approach, where you track the maximum amount of money that can be robbed up to each house, considering the constraint of not robbing adjacent houses.

Here's an optimized version of your solution:

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

        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]

In this version, the dp list is used to store the maximum amount of money that can be robbed up to each house. For each house starting from the third one (index 2), you have two choices:

• Rob the current house, and add its value to the maximum amount robbed up to two houses before (nums[i] + dp[i - 2]).
• Don't rob the current house, and keep the maximum amount robbed up to the previous house (dp[i - 1]).

Finally, the last element in the dp list (dp[-1]) will have the maximum amount that can be robbed without alerting the police.

This solution is more straightforward as it directly calculates the maximum robbed amount at each step without needing to maintain three separate variables (first, second, third). The use of a dynamic programming array (dp) makes the logic clearer and more aligned with typical dynamic programming solutions.