灵神基础算法精讲-17-学习笔记

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路

参考子集型回溯，有（1）选或不选（2）选哪个，这两种思路，对于很多动态规划问题，也可以用这两种思路来思考。

对于这一题，先把它看作一道回溯题，那么要把一个大问题变成规模更小的子问题，从第一个房子或者最后一个房子开始思考是最容易的，因为它们受到的约束最小。比如考虑最后一个房子选还是不选，如果不选，那么问题就变成 n-1 个房子的问题，如果选，那么问题就变成 n-2 个房子的问题，不断这样思考下去，就可以得到一棵搜索树了。

由于在选的情况下，相邻的房子是不能选的，所以直接递归到 n-2 个房子。把上述思考过程抽象一下，当枚举到第 i 个房子选或者不选的时候，就确定了递归参数中的 i，dfs(i) 的含义就是从前 i 个房子中得到的最大金额和。如果不选第 i 个房子，问题就变成从前 i-1 个房子中得到的最大金额和，如果选第 i 个房子，问题就变成从前 i-2 个房子中得到的最大金额和。

回溯三问：

1. 当前操作：枚举第 i 个房子选还是不选
2. 子问题：从前 i 个房子中得到的最大金额和
3. 下一个子问题：分类讨论：（1）不选：从前 i - 1 个房子中得到的最大金额和（2）选：从前 i - 2 个房子中得到的最大金额和

dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])

在定义 DFS 或者 DP 数组的含义时，它只能表示从一些元素中算出的结果，而不是从一个元素中算出的结果。

做法

回溯

class Solution:
    def rob(self, nums):
        n = len(nums)
        def dfs(i):
            if i < 0:
                return 0
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            return res
        return dfs(n - 1)

记忆化搜索

class Solution:
    def rob(self, nums):
        n = len(nums)
        cache = [-1] * n
        def dfs(i):
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            cache[i] = res
            return res
        return dfs(n - 1)

时间复杂度计算方法

时间复杂度 = 状态个数 x 单个状态所需要的计算时间，状态个数是 O(n)，单个状态的计算时间是 O(1)，所以时间复杂度就是 O(n)

递推

直接从最下面开始往上计算，把 dfs 改成 f 数组，把递归改成循环。但这样写的话，需要对 i = 0, i = 1 的情况特殊处理，因为会产生负数下标。为了避免出现负数下标，可以在 f 数组前面插入 2 个 0，把所有的 i 都 + 2。

class Solution:
    def rob(self, nums):
        n = len(nums)
        f = [0] * (n + 2)
        for i, x in enumerate(nums):
            f[i + 2] = max(f[i + 1], f[i] + x)
        return f[n + 1]

优化空间复杂度

f[i] 是当前要算的，f[i - 1] 是上一个算出来的，f[i - 2]是上上一个算出来的，也就是说，要计算一个 f[i]，只需要知道它上一个状态和上上一个状态的值。此外，对于 f[i + 1] 来说，f[i] 就变成它的上一个状态了，f[i - 1] 就变成它的上上一个状态了，那么用 f0 表示上上一个，f1 表示上一个，就可以得到 newF = max(f1, f0 + nums[i])，f0 = f1, f1 = newF。

class Solution:
    def rob(self, nums):
        n = len(nums)
        f0 = f1 = 0
        for i, x in enumerate(nums):
            new_f = max(f1, f0 + x)
            f0 = f1
            f1 = new_f
        return f1