难度: Medium
一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：nums = [1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：nums = [2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400注意：本题与主站 198 题相同： https://leetcode-cn.com/problems/house-robber/
运行时间: 20 ms
内存: 16.2 MB
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
cache={}
def dfs(nums,c,money):
n=len(nums)
if c==n-1 or c==n-2:return nums[c]
elif c>=n: return -1
if c in cache:return cache[c]
res=[dfs(nums,c+1,money),dfs(nums,c+2,money)+nums[c],dfs(nums,c+3,money)+nums[c]]
# res=[dfs(nums,c+1,money),dfs(nums,c+2,money)+nums[c]]
max_i=max(enumerate(res),key=lambda x:x[1])
cache[c]=max_i[1]
return max_i[1]
n=len(nums)
if n==1:return(nums[0])
if n==2:return(max(nums[0],nums[1]))
else:
return(dfs(nums,0,0))
这道题的题解采用了递归加备忘录的方法来求解。小偷有一个选择，他可以选择从当前的房子开始偷或者跳过一两个房子后再开始偷。基本的递归策略是：考虑当前位置c，小偷可以选择偷这个房子然后跳过下一个，直接从c+2开始或者从c+3开始（即不偷当前房子，也可能不偷下一个，但考虑后一个），或者不偷当前房子直接从c+1开始。结果是这些选择中可以偷到的最大金额。使用备忘录（cache）来存储已经计算过的结果，避免重复计算，提高效率。
时间复杂度: O(n)
空间复杂度: O(n)
from typing import List
# Solution class to solve the problem
class Solution:
def rob(self, nums: List[int]) -> int:
# Cache to store the results of subproblems
cache = {}
# Helper function to perform depth-first search
def dfs(nums, c, money):
n = len(nums)
# Base cases to handle the last one or two houses
if c == n-1 or c == n-2: return nums[c]
# Return negative if index is out of bounds
elif c >= n: return -1
# Use cached value if available
if c in cache: return cache[c]
# Calculate the maximum money from current house and two options ahead
res = [dfs(nums, c+1, money), dfs(nums, c+2, money) + nums[c], dfs(nums, c+3, money) + nums[c]]
# Determine the maximum value and index
max_i = max(enumerate(res), key=lambda x: x[1])
# Store the result in cache and return
cache[c] = max_i[1]
return max_i[1]
# Initial conditions for arrays of length 1 and 2
if n == 1: return(nums[0])
if n == 2: return(max(nums[0], nums[1]))
# Start the dfs from the first house
else: return(dfs(nums, 0, 0))
在这个问题中，选择从c+2或c+3开始是基于问题的最优子结构。当小偷决定偷c位置的房子时，他必须跳过c+1位置的房子，因此下一个可能的房子是c+2。同时，考虑到可能跳过更多房子以获取最大收益，算法也探索了从c+3开始的情形。通常，不需要从c+4或更远的房子开始，因为这些情况已经被c+2和c+3的结果覆盖，即从c+2或c+3开始的递归调用会进一步探索从c+4开始的情况。
参数`money`在这个递归函数的实现中确实没有被使用，它可能是在设计函数时预留的，用于可能的功能扩展或错误地从另一个类似函数复制过来的。在当前的函数实现中，`money`是多余的，因为它没有参与到任何计算逻辑中。正确的做法应该是从函数的参数列表中移除它，以避免混淆和可能的性能损失。
备忘录`cache`确保了计算效率通过存储已经计算过的结果，避免了重复计算。在`dfs`函数中，每次计算一个位置c时，都会考虑三种选择：只偷下一个房子的情况（c+1），偷当前房子与后面第二个房子的组合（c+2加当前房子），以及偷当前房子与后面第三个房子的组合（c+3加当前房子）。函数通过递归调用自身来探索所有这些选择，并使用`max`函数来比较这些选项，确保选出最大金额。因此，通过这种方式，`cache`确实存储了从每个位置开始，考虑所有可能组合后能偷到的最大金额。