LeetCode 198打家劫舍DP解法问题：列表莫名添加元素求助

核心错误1：条件分支未互斥，导致额外元素插入 #

你的代码中循环内的三个条件是独立的if，而非互斥的elif，Python中else会与最近的未配对if绑定。当i=0时：

• 执行if i==0的逻辑，向sum添加nums[0]（即2）
• 由于i!=1，会进入第二个if对应的else块，执行sum.append(max(nums[0]+nums[-2], nums[-1]))
  • 此时nums[-2]是3，nums[-1]是1，计算得max(2+3,1)=5，所以sum被额外添加了5，这就是你看到的莫名出现的元素。

核心错误2：DP状态转移方程错误 #

正确的打家劫舍DP状态应该是：dp[i]表示前i+1个房子能偷到的最大金额，转移方程为：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
而你的代码中用了max(nums[i]+nums[i-2], nums[i-1])，直接使用原数组的值而非之前计算的最大金额，完全偏离了DP的核心逻辑。

修复后的代码 #

from typing import List

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

简化优化（空间优化） #

由于每次只需要前两个状态的值，可以不用维护整个数组，进一步节省空间：

from typing import List

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

内容的提问来源于stack exchange，提问作者Peter Lee