状态定义？状态转移方程？
1. 打家劫舍
1.1 解题思路
理解题目：我需要选择一些数，使它们的和最大，并且选择的数字不能是相邻的。
我们先将这道题看成回溯。
考虑最后一个房子选或不选。
如果不选，问题就变成 \(n-1\) 个房子的问题。
如果选，问题就变成 \(n-2\) 个房子的问题。
回溯三问：
当前操作？枚举第 \(i\) 个房子选/不选
子问题？ 从前 \(i\) 个房子中得到的最大金额和
下一个子问题？ 分类讨论：
不选：从前 \(i-1\) 个房子中得到的最大金额和
选：从前 \(i-2\) 个房子中得到的金额和
\[dfs(i)=max(dfs(i-1), dfs(i-2)+nums[i])
\]
1.2 代码实现
1.2.1 回溯
点击查看代码
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();auto dfs = [&](this auto&& dfs, int i) -> int {if (i < 0) {return 0;}return max(dfs(i - 1), dfs(i - 2) + nums[i]);};return dfs(n - 1);}
};
- 时间复杂度：\(O(2^n)\)
- 空间复杂度：\(O(n)\)
1.2.2 自顶向下：记忆化搜索
点击查看代码
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();vector<int> dp(n, -1);// dp[i]表示偷盗第 $i$ 家所能获得的最大金额。auto dfs = [&](this auto&& dfs, int i) -> int {if (i < 0) {return 0;}int& ans = dp[i];if (ans != -1) {return ans;}ans = max(dfs(i - 1), dfs(i - 2) + nums[i]);return ans;};return dfs(n - 1);}
};
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
1.2.3 自底向上：递推
如何把记忆化搜索改成递推呢？
\(dfs\rightarrow\) \(f\) 数组
\(递归\rightarrow\) 循环
\(递归边界\rightarrow\) 数组初始值
已知：\(dfs(i)=max(dfs(i-1), dfs(i-2)+nums[i])\)，
可以得到：
\(f(i)=max(f(i-1),f(i-2)+nums[i])\)
点击查看代码
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();// 相当于在数组最前面插入-1，-2两个状态vector<int> f(n + 2, 0);for (int i = 0; i < n; ++i) {f[i + 2] = max(f[i + 1], f[i] + nums[i]);}return f[n + 1];}
};
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
1.2.4 优化空间复杂度
\(f(i)\) 依赖于 上一个状态 \(f(i-1)\) 和 上上一个状态 \(f(i-2)\)。
于是我们可以用 \(f0\) 表示上上一个，\(f1\)表示上一个。
点击查看代码
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();int f0 = 0, f1 = 0;for (int i = 0; i < n; ++i) {int new_state = max(f1, f0 + nums[i]);f0 = f1;f1 = new_state;}return f1;}
};
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)