LeetCode 198 - 打家劫舍

题目

解题思路

这是一个典型的动态规划问题。对于每个房屋，我们有两种选择：

1. 偷这个房子：不能偷相邻的前一个房子，但可以偷前前一个房子。
2. 不偷这个房子：最大金额就是偷到前一个房子为止的最大金额。

定义状态：

• dp[i] 表示偷窃前 i 个房屋能够获得的最大金额。

状态转移方程：

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

含义：

1. 当 dp[i-1] > dp[i-2] + nums[i] 时，选择 dp[i-1]。
2. 否则选择 dp[i-2] + nums[i]。

边界条件：

• dp[0] = nums[0]：只有一个房子时。
• dp[1] = max(nums[0], nums[1])：有两个房子时，选择金额较大的那个。

代码实现

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
            
        # 初始化dp数组
        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], dp[i-2] + nums[i])
            
        return dp[-1]

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。
• 空间复杂度：O(n)，需要一个 dp 数组来存储状态。

优化空间复杂度

注意到我们每次状态转移只需要前两个状态，因此可以只用两个变量来维护状态，将空间复杂度优化到 O(1)：

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
            
        prev2, prev1 = nums[0], max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            current = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, current
            
        return prev1

总结

以下是我自己的实现方法。发现 max 函数时间消耗比我的大，所以用大小判断时间更短。但当时没有想到通用公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

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


        dp = [0]*l

        dp[0]= nums[0]
        dp[1]= nums[1]
        # pre2_maxvalue 记录的是，如果盗窃当前房子，则当前房子index-2前的最大盗窃总额。index-2 因为不相邻
        # i 为2 的话
        pre2_maxvalue = dp[0]
        for i in range(2,l):
            if dp[i-2]>pre2_maxvalue:
                pre2_maxvalue = dp[i-2]
            
            dp[i] = pre2_maxvalue+nums[i]
        
        return max(max(dp[l-3],dp[l-1]),max(dp[l-2],dp[l-4]))

题目进阶

链接