难度: Medium
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400运行时间: 16 ms
内存: 15.9 MB
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
f = [0] * len(nums)
f[0] = nums[0]
f[1] = nums[1]
f[2] = max(nums[1], nums[0]+nums[2])
for i in range(3, len(nums)):
f[i] = max(f[i-1], f[i-2]+nums[i], f[i-3]+nums[i])
return f[-1]
# f[n]小偷到达第n个房间能偷到的最多钱
# f[n+1] = f[n]: 如果第n间被偷
# f[n+1] = f[n-1] + nums[n+1] : 如果第n间不偷
# 比较两种情况下的最大值
# f[0] = 2
# f[1] = 7
# f[2] = 11
# f[3] = 11
# f[4] = 12
这个题解使用动态规划的思路来解决打家劫舍问题。对于第i个房间，小偷有两种选择：偷或者不偷。如果偷第i个房间，那么第i-1个房间就不能偷，总金额等于f[i-2]+nums[i]；如果不偷第i个房间，那么总金额等于f[i-1]。状态转移方程为：f[i] = max(f[i-1], f[i-2]+nums[i])。最后返回f[-1]即可获得最大金额。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
# 初始化状态数组
f = [0] * len(nums)
f[0] = nums[0]
f[1] = nums[1]
f[2] = max(nums[1], nums[0]+nums[2])
# 状态转移
for i in range(3, len(nums)):
f[i] = max(f[i-1], f[i-2]+nums[i], f[i-3]+nums[i])
# 返回最大金额
return f[-1]
在打家劫舍问题中，如果小偷选择偷第三个房间（即nums[2]），则不能偷第二个房间（nums[1]），但可以考虑偷第一个房间（nums[0]）。因此，最优解是考虑不偷第二个房间的最大值(nums[0]+nums[2])和偷第二个房间的值(nums[1])的较大者。前三个房间的可能组合实际上已经包括在这两种计算中，因为第一个房间和第三个房间的组合已经提供了跳过第二个房间的最大值。
通常的动态规划解法`f[i] = max(f[i-1], f[i-2] + nums[i])`仅考虑了连续两个房间不被偷的情况。而扩展到`f[i] = max(f[i-1], f[i-2]+nums[i], f[i-3]+nums[i])`的目的是为了增加更多的灵活性，考虑可能的战略，比如跳过两个房间再偷窃，这可能在某些特定的输入情况下提供更大的金额。但这种方法需要验证其逻辑正确性和是否能带来更多收益。
如果数组长度非常短，状态转移方程`f[i] = max(f[i-1], f[i-2]+nums[i], f[i-3]+nums[i])`可能需要调整。特别是当数组长度为3时，`f[i-3]+nums[i]`将会访问不存在的数组元素，因此需要特别注意边界条件的处理。对于长度为3或4的数组，应该直接计算可能的最大值，而不是使用复杂的状态转移方程。
题解中的动态规划解法没有明确指出对所有边界条件的处理，特别是当数组中所有元素都是0的情况。理论上，动态规划数组`f`的初始化和状态转移应能正确处理全0的情况，因为状态转移方程自然会将0作为可能的返回值。然而，明确检查并测试这类边界情况始终是推荐的做法，以确保算法的健壮性。