DP-打家劫舍-LeetCode 198/213

198. 打家劫舍

198.打家劫舍

定义dp[k]为偷到第k间屋子能获得的最大金额。

image.png

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

        dp = [0] * n 
        dp[0] = nums[0] 
        dp[1] = max(nums[1], nums[0])
        for i in range(1, n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[n-1]

空间优化：当前状态只与前两个状态有关：

    def rob(self, nums):
        n = len(nums) 
        if n == 0: return 0
        elif n <= 2: return max(nums)
        pre, cur = nums[0],  max(nums[0], nums[1])
        for i in range(2, n):
            res = max(pre + nums[i], cur)
            pre, cur = cur, res 
        return res

213. 打家劫舍 II

213.打家劫舍 II

解题思路：把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。
1.不偷最后一间
2.不偷第一间
结果取1、2最大值。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums) 
        if n == 0: return 0
        elif n <= 3: return max(nums)
        return max(self.eastRob(nums[1:]), self.eastRob(nums[:n-1]))
    
    def eastRob(self, nums):
        n = len(nums) 
        if n == 0: return 0
        elif n <= 2: return max(nums)
        pre, cur = nums[0],  max(nums[0], nums[1])
        for i in range(2, n):
            res = max(pre + nums[i], cur)
            pre, cur = cur, res 
        return res