为避免负数下标，也可以让 i 从2 开始
python
class Solution:
def rob(self, nums: List[int]) -> int:
# dfs
@cache
# n 属于 [-1, n-1] 有n+1个数
def dfs(n):
if n < 0:
return 0
return max(dfs(n-1), dfs(n-2)+nums[n])
return dfs(len(nums)-1)python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * (n+2) # 有n+2个数!!! 属于 [0, n+1]
# n+2来自于i+2，dfs的i最大是n-1，经过n+2之后，就是n+1，所以长度为n+2
# i 只负责对应 n+2
for i, x in enumerate(nums):
f[i+2] = max(f[i+1], f[i]+x)
return f[n+1]有不少同学问我为什么 nums【i】 中的 i 不需要 +2。
另外一种理解方式是，我们只是在 f 数组的开头插入了两个状态，对应记忆化搜索中的 dfs(-2) 和 dfs(-1)，
这只会影响到 f 的下标，不会影响到 nums 的下标。