跟着灵茶山艾府大佬学习算法思路的day12（并没有在一个月内掌握hot100）
b站链接如下：
对于很多动态规划问题，也可以用选或不选和选哪个的思路来思考。
回溯的思路里面其实也有拆分子问题的特点，但是我们如果要给回溯和动态规划分类，我们一般认为回溯是遍历视角，动态规划是子问题视角，这是为什么呢？
因为关键区别在于：同一个子问题会不会被重复遇到。对于回溯而言，每个节点都是新的，因为无论是选或不选或者选哪个，每个节点的path都不同，都是不同的子问题；而对于动态规划，同一个子问题可能被多次遇到（不同路径可能到达同一个子问题）。
虽然基于递归，但动态规划最好的解法往往是递推，递推使用的正是递归得到的状态转移方程。从问题拆解的角度来看，递归是自顶向下，递推是自底向上，这里的自顶向下和之前二叉树说的自底向上并不矛盾，二叉树说的是计算发生在哪，递归到底再往回算，计算是自底向上；而DP 这里说的是从哪出发：从原问题出发拆解，还是从 base case 出发构造。
回溯 动态规划 子问题唯一性 path 不同 → 子问题不同 state 相同 → 子问题相同 能否缓存 不能，每个都得走 能，算过就不用再算 关注点 走了哪条路（路径） 走到某个状态的最优值（结果） 视角 遍历：我要走完所有路 子问题：我要算出每个状态的答案 一开始就思考递推，往往是很困难的，因为递推直接使用了通过递归思路得到的状态转移方程。如果没有二叉树递归和回溯前置基础，是不容易想到先从递归处理动态规划的，如果直接看递推的最优解，很多时候并不能很好地理解动态规划的核心思想，这也是学习动态规划的难点之一。
打家劫舍 题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
思路：
可以先将这道题看作一道回溯题，如果要将一个大问题变为规模更小的子问题，显然从第一个或最后一个房子来思考，所受到的约束是最小的。
如果从尾部开始考虑，可以得到这样一棵搜索树。
这里要分清第i个和前i个的概念，在定义dfs或者dp数组的含义时，它只能表示从一些元素中算出的结果，而不是从一个元素中算出的结果。
另一点是这里没有把得到的金额和作为递归的入参，而是当做了返回值。
根据上述的思路，可以先写出最直接的逻辑：
但这种情况类似于回溯，时间复杂度是指数级的，会超时，因此需要考虑如何优化。
此时回到原先的树状图，我们可以发现树中具有重复的子问题，这里又算了一次dfs(2)。因此我们可以考虑在第一次计算时把计算结果存储到一个cache数组或者哈希表中，便于再第二次遇到重复的子问题时，可以直接取出对应结果，不必重复计算。结果树是呈指数级增长的，使用额外空间的消耗的空间开销一定会远大于不使用额外空间而无法避免的时间开销。
这样优化后，树中只有了o(n)个节点，因此时间复杂度也优化到了o(n)。使用了o(n)级的空间开销，将时间开销从o(n^2)降低到了o(n)。
还有办法是能够将时间复杂度降低到o(1)的，根据状态转移方程，我们已知哪些节点会作为选或不选的结果被归入到哪些节点下方，因此我们能够去掉递归中的递，只留下归的过程。也就是直接从最下方开始往上计算，也就是递推。
递推构建的灵魂在于，递归的转移方程就是递推的转移方程，只是计算顺序反过来。思考流程会是先写递归想清楚转移方程，然后照抄方程翻转方向，最后实现递推。
代码：
没有记忆化搜索的超时版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var rob = function(nums) {
const n = nums.length;
const dfs = (i) => {
if (i < 0) {
return 0;
}
const res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
return res;
}
return dfs(n - 1);
};
使用数组或映射加入记忆化搜索：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var rob = function(nums) {
const n = nums.length;
const memo = new Array(n).fill(-1);
const dfs = (i) => {
if (i < 0) {
return 0;
}
if (memo[i] !== -1) return memo[i]; // 查
const res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
memo[i] = res; // 存
return res;
}
return dfs(n - 1);
};
将递归调用1:1变化为递推（此时空间复杂度仍为o(n)）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var rob = function(nums) {
const n = nums.length;
const dp = new Array(n);
// 由于下标不能小于0，所以前两个位置手动初始化
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// 转移方程照抄，dfs(i-1) 变 dp[i-1]
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
};
最后优化为空间复杂度为o(1)的滚动变量：
1
2
3
4
5
6
7
var rob = function(nums) {
let f0 = 0, f1 = 0;
for (const x of nums) {
[f0, f1] = [f1, Math.max(f1, f0 + x)]
}
return f1;
};
总结：
关键在于能够将原问题转化为递归问题处理，然后意识到子问题的重复，增加备忘录（此时的解法已经实际可用），再进一步改写为递推，最后再优化出滚动变量。
① 递归（暴力）
对第 i 栋房子，两个选择：抢（跳过前一个）或不抢
1
dfs(i) = max(dfs(i-1), dfs(i-2) + nums[i])
指数级时间，大量重复计算。
② 递归 + 备忘录
加个数组缓存结果，每个子问题只算一次。O(n) 时间，O(n) 空间。
③ 递推（自底向上）
翻转计算方向，用 for 循环填 dp 数组。O(n) 时间，O(n) 空间。
④ 滚动变量（空间优化）
dp[i] 只依赖前两个值，两个变量滚着走。O(n) 时间，O(1) 空间。
最难的两个点在于：
- 想出转移方程，”对第 i 栋房子，抢还是不抢”这个二选一怎么想到的，这步没有固定套路，靠对问题的理解
- 定义状态，
dp[i]到底代表”抢第 i 栋”还是”前 i 栋的最优解”，定义错了方程就推不对
最后，假设小偷想知道的不只是总金额，还要知道偷哪些房屋时，就需要使用空间优化前的写法，因为需要一个规模为n的数组记录所有房子的情况。