算法分析-打家劫舍

继续尝试：打家劫舍。

分析

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

就是说，在数组中找到一些数加起来之和要最大，但是这些数在数组中不能是相邻的。

简单尝试了一下，将数组中奇数位和偶数位加起来比较，然后返回大的那个数。但是遇到测试用例[2, 1, 1, 2]的时候就不对了，按照我的算法只能得到3，但是它最优解是4。 这样好像显得我这个小偷不够专业，于是我拜师求艺，得到了一本叫动态规划的功法。

动态规划

功法的核心是，到第 i 间房时，有两个选择：

• 偷这间：nums[i] + 第 i-2 间的最优解

• 不偷这间：第 i-1 间的最优解 取两者最大值，就是第 i 间房的最优解。

通俗地说，假设我们现在已经偷过了一部分，并且前面已经得到了最多的钱，那么我们面对当前这家有两个选择： 如果要偷这家，那么上一家是不能偷的，所以最多收获是前面偷到第 i-2 家时能偷到的最多的钱，加上现在要偷的这家的钱。 如果不偷这家，那么最多的收获就是前面偷到第 i-1 家时能偷到的最多的钱。

我们每经过一家，就记录下 y："偷这家时，账户里最多有多少钱"；n："不偷这家时，账户里最多有多少钱"。那么有：

n = max(last_y, last_n) # 不偷，拿上一家偷和不偷的最大值。

y = last_n + nums[i] # 偷，拿上上家偷和不偷的最大值，再加上现在偷的这家。而上上家偷和不偷的最大值就是上一家不偷的情况，也就是 last_n。

我们以 [2, 1, 1, 2] 为例：

# 偷第一家的时候：y = 0 + 2 = 2, n = 0，就只有一家，偷的话能有 2 块钱，不偷的话没钱。最优解是 2 块钱，即偷。
# 偷第二家的时候：y = 0 + 1 = 1, n = 2，偷这家的话，那么第一家就不能偷，只得到 1 块钱。坚持偷第一家而不偷这一家的情况，得到的是 2 块钱，这一步的最优解是 2 块钱，即不偷。
# 偷第三家的时候：y = 2 + 1 = 3, n = 2，偷这家的话我们就不能偷上一家，而从上上家得到最好的结果是 2，加上这家的 1 块钱，能有 3 块钱。如果不偷的话，身上的钱就是前面两家偷的钱，我们已经知道前面两家最多能偷到 2 块钱。这一步的最优解是 3，即偷。
# 偷第四家的时候：y = 2 + 2 = 4, n = 3，偷这家的话我们就不能偷上一家，而从上上家得到最好的结果是 2，加上这家的 2 块钱，能有 4 块钱。如果不偷的话，身上的钱就是前面三家偷的钱，我们已经知道前面三家最多能偷到 3 块钱。这一步的最优解是 4，即偷。

经过以上分析，代码实现起来就很简单了：

def rob(self, nums: list[int]) -> int:
    y, n = 0, 0
    for i in range(len(nums)):
        last_y, last_n = y, n
        y = last_n + nums[i]
        n = max(last_y, last_n)
    return max(y, n)

因为是相邻的不能偷，所以只用考虑前面的两步。要偷这家，前面最近的只能偷到 i-2，偷过 i-1 就不能偷这家了。 假如是每隔两家才能偷一次，那么就要考虑偷前面 i-3、i-2、i-1 家的情况，本质是：跟谁冲突，就往前面翻过冲突范围去看。冲突越深，依赖的历史越远、状态变量越多。这就是 DP 里"状态转移窗口"的概念——窗口宽度 = 约束距离。

一趟遍历，两个变量。$O(n)$ 时间复杂度、$O(1)$ 空间复杂度。

总结

概念有点抽象，我也是思考了两个小时才略微懂一点皮毛。

第一次接触动态规划的概念，对于这种将前面计算的结果用于后面计算的思路，还是感觉很新奇的。 靠前面的结果一点点堆积起来得到最终的结果，不用关心前面是怎样的路径、是哪些数相加。 从很小的子问题开始找到最优解，后续在最优解上继续叠加，得到全局最优解。

动态规划的核心就是一句话：把大问题拆成小问题，每个小问题的答案存下来，后面直接用不再重算。