Leetcode Link: 198. 打家劫舍 - 力扣（LeetCode）
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
解法一
从暴力递归到动态规划
暴力递归
读题分析，似乎是从左到右的尝试模型
对于 idx 位置的情况讨论，初想好像是只有相邻第一个位置的不能用，即可以分解成 idx+2, idx+3, idx+4… 的情况
然而，多思考一些先验，既然我们希望抢最多的钱，我们肯定希望抢的位置越多越好，所以 idx+2, idx+3 就能够遍历到所有了（尝试举例子，没有反例），因此我们将 idx 位置的情况讨论成 idx+2, idx+3。
但是这样的分类讨论一定要考虑0位置和1位置谁先开始，如果只是0位置开始，则肯定缺少一种情况
class Solution:
def rob(self, nums: List[int]) -> int:
return max(self.process(nums, 0), self.process(nums, 1))
def process(self, nums, idx):
# base case
# 当超过长度的时候，抢到0元
if idx >= len(nums):
return 0
p1 = self.process(nums, idx+2) + nums[idx]
p2 = self.process(nums, idx+3) + nums[idx]
return max(p1, p2)动态规划
显然是改写成 1 维动态规划，方向右到左。
改写的时候要注意，无论在哪一个位置，我们都一定需要记得加上当前位置抢的钱，如果直接抄上面的代码 max(A+nums[idx], B+nums[idx])作为递推公式，一定是错误的，因为越界之后是无法“抢”到当前位置的钱的。
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0 for _ in range(len(nums)+1)]
for i in range(len(nums)-1, -1, -1):
if i + 2 < len(nums):
dp[i] = max(dp[i], dp[i+2])
if i + 3 < len(nums):
dp[i] = max(dp[i], dp[i+3])
dp[i] += nums[i]
return max(dp[0], dp[1])解法二（解法一改进一下）
在暴力递归中，能不能考虑合并主函数中的两种情况呢？
暴力递归
可以，对于当前位置，就是要和不要两种情况，要了就了走两步，不要就走一步
class Solution:
def rob(self, nums: List[int]) -> int:
return self.process(nums, 0)
def process(self, nums, idx):
if idx >= len(nums):
return 0
p1 = self.process(nums, idx+1)
p2 = self.process(nums, idx+2) + nums[idx]
return max(p1, p2)动态规划
好改！但是注意抢当前位置的时候！怎么改！不要忘记“抢”！
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0 for _ in range(len(nums)+1)]
# 最后一个位置可以不用初始化，因为dp初始化就是0
for i in range(len(nums)-1, -1, -1):
dp[i] = dp[i+1]
# 注意下面，开始写错了
# 开始没写else
if i + 2 <= len(nums):
dp[i] = max(dp[i], dp[i+2]+nums[i])
else:
dp[i] = max(dp[i], nums[i])
return dp[0]