第40天，动态规划part07，动态规划经典题型“打家劫舍”(ง •_•)ง，编程语言：C++
目录
198.打家劫舍
213.打家劫舍II
337.打家劫舍III
总结
198.打家劫舍
文档讲解：代码随想录打家劫舍
视频讲解：手撕打家劫舍
题目： 198. 打家劫舍 - 力扣（LeetCode）
学习：本题根据题意，对于一个房间来说，我们有偷和不偷两种选择。我们在选择每一间房间偷还是不偷的时候，都是为了得到最大的金钱数。我们从动规五部曲出发进行分析。
1.确定dp数组以及下标的含义：我们可以设置一个一维dp数组，dp[i]表示从0-i个房间，我们能够偷到的最大值。
2.确定递推公式：dp[i]能够由谁得来呢？这取决于我们对i房间是偷还是不偷。如果我们偷i房间，则dp[i]应该是dp[i - 2]+nums[i]，意味着隔一个房间不偷加上本房间的财富的价值。如果我们不偷i房间，则dp[i]应该是dp[i - 1]，也即不偷这个房间，我们能偷的最大价值就应该是上一个房间能够偷的最大价值。最后我们可以得到递推公式为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。
3.初始化dp数组：由递推公式我们可知需要初始化至少两个数，dp[0]和dp[1]。显然dp[0]表示0号房间的价值，dp[0] = nums[0]。dp[1]则不能直接赋为nums[1]因为对于dp[1]来说也可以选择取或者不取nums[1]，因此dp[1]应该是max(nums[0], nums[1])。
4.确定遍历顺序，从i = 2开始遍历到最后一个节点。
5.举例dp数组
代码：
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
//1.确定dp数组以及下标的含义, dp[j]表示偷窃0-i个房间能够得到的最高金额
vector<int> dp(nums.size(), 0);
//2.确定递推公式：dp[i] = max(dp[i-1],dp[i - 2] + nums[j]);
//3.初始化dp数组：
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
//4.确定遍历顺序
for(int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i-1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};213.打家劫舍II
文档讲解：代码随想录打家劫舍II
视频讲解：手撕打家劫舍II
题目：213. 打家劫舍 II - 力扣（LeetCode）
学习：本题与上一题不同之处在于，本题是一个环形数组，头部和尾部是连在一起的，这会导致第一个房间和最后一个房间不能同时取用。
但换言之我们可以分开讨论这两种情况。我们可以先考虑不包含尾元素的情况，也就是仅考虑[0, nums.size() - 2]的这个区间，对于这个区间来说，我们要求得能够得到的最大金额，就和上一题是一样的了，采用的方法也相同。
同理我们可以再考虑不包含头元素的情况，也就是仅考虑[1, nums.size() - 1]这个区间，对于这个区间来说，同样得到最大金额的办法和上一题一样。最后我们再取这两个方法得到的最大值之中的更大的那个即可。
接着我们来考虑，这样会不会导致出现遗漏呢，对于第一种不考虑尾元素的情况，假如得到的最大值的取用中取用了头元素，那即使是考虑了尾元素，我们也不能取；同理对于第二种不考虑头元素的情况，假如得到的最大值的取用中取用了尾元素，那即使考虑了头元素，我们也还是不能取；而第三种情况假如头元素和尾元素都没有取用，那就意味着[1, nums.size() - 2]中我们能够得到最大值，即使加上头元素和尾元素，也无法得到更大的值，因为第一种情况和第二种情况，已经把这种可能性包括了。
因此，我们可以分两次得到两种可能性的值，最后得到最大的。
代码：要十分注意起始遍历点和终止遍历点的位置。
//时间复杂度O(n) 2n
//空间复杂度O(n)
class Solution {
public:
int robrange(vector<int>&nums, int start, int end) {
if(start == end) { //nums.size()为2的情况
return nums[start];
}
//1.确定dp数组以及下标含义
vector<int> dp(nums.size());
//2.确定递推公式：dp[i] = max(dp[i-1],dp[i - 2] + nums[i]);
//3.初始化dp数组
dp[start] = nums[start];
dp[start + 1] = max(nums[start], nums[start + 1]);
//4.确定遍历顺序
for(int i = start + 2; i <= end; i++) {
dp[i] = max(dp[i-1],dp[i - 2] + nums[i]);
}
return dp[end];
}
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
int result1 = robrange(nums, 0, nums.size() - 2); //不考虑尾元素
int result2 = robrange(nums, 1, nums.size() - 1); //不考虑头元素
return max(result1, result2);
}
};337.打家劫舍III
文档讲解：代码随想录打家劫舍III
视频讲解：手撕打家劫舍III
题目： 337. 打家劫舍 III - 力扣（LeetCode）
学习： 本题与上两题不同在于，从一个一维数组变成了一颗二叉树，增大了遍历的复杂度，本质还是隔一个搜一个，但需要在动规的过程中加入树的遍历。
我们尝试从动规五部曲进行分析：
1.确定dp数组，我们尝试使用一个map来保存各节点map<Treenode*,int>dp，dp[i].second表示i节点之下能够得到的最大金额。
2.确定递推公式：同样分两种情况，取用当前节点i，dp[i] = i - >val + dp[i->left->left] + dp[i->left->right] + dp[i->right->right] + dp[i->right->left]，也就是当前节点的值，加上它的所有孙子的值。如果不取用节点i呢，dp[i] = dp[i->left] + dp[i->right]，也就是它的左右孩子的值。
可以发现到这里，在实际使用的时候，我们需要先遍历所有的节点，且确定哪些节点是哪些节点的孙子孩子，这在实际中是很困难的，因此本题的dp数组的设置，与我们常规的dp数组的设置不同，本题的递推公式主要提供了计算的方式。
方法一：暴力搜索
根据递推公式，我们可以采取暴力搜索的方式来得到最大值：
//时间复杂度(n^2)
//空间复杂度O(logn)
class Solution {
public:
int rob(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return root->val;
// 偷父节点
int val1 = root->val;
if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left，相当于不考虑左孩子了
if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right，相当于不考虑右孩子了
// 不偷父节点
int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
return max(val1, val2);
}
};方法二：记忆化递推
实际上我们也能够使用上述递推公式的办法，我们可以一边遍历一边存储最大值的方式进行，这样能够在暴力搜索的基础上，降低时间复杂度，减少重复计算：
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
unordered_map<TreeNode* , int> umap; // 记录计算过的结果
int rob(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return root->val;
if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回
// 偷父节点
int val1 = root->val;
if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left
if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right
// 不偷父节点
int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
umap[root] = max(val1, val2); // umap记录一下结果
return max(val1, val2);
}
};
方法三：动态规划
本题还有个是将动态规划和递归结合的方法，结合递归三部曲和动规五部曲进行。
1.确定递归函数的参数和返回值：
参数显然为各节点，返回值我们设置为dp值，这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
vector<int> robTree(TreeNode* cur) {换言之我们设置了一个dp数组，dp[0]表示不取用该点时的最大金钱数，dp[1]表示取用该点时的最大金钱数。为啥要设置0，1两种可能，也是为后面的遍历做准备。
2.确定终止条件：遍历到空节点返回
if (cur == NULL) return vector<int>{0, 0};3.确定遍历顺序：采用后序遍历
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右4.确定递推公式：
int val1 = cur->val + left[0] + right[0]; //意味着取用该点时，最大值为该点的值加上左右孩子不用的情况下最大的值。
int val2 = max(left[0], left[1]) + max(right[0], right[1]); //意味着不取用该点时，能够得到的最大值5.举例推导dp数组：
代码：最后总结得到代码
//时间复杂度O(n)
//空间复杂度O(logn)
class Solution {
public:
//动态规划+递归
//1.确定参数及返回值
vector<int> traversal(TreeNode* cur) {
//2.确定终止条件
if(cur == nullptr) return {0,0};
//3.确定遍历顺序
vector<int> left = traversal(cur -> left);
vector<int> right = traversal(cur -> right);
//4.确定递推公式
int val1 = cur->val + left[0] + right[0]; //意味着取用该点时，最大值为该点的值加上左右孩子不用的情况下最大的值。
int val2 = max(left[0], left[1]) + max(right[0], right[1]); //意味着不取用该点时，能够得到的最大值
//返回数值
return {val2, val1};
}
int rob(TreeNode* root) {
vector<int> dp = traversal(root);
return max(dp[0], dp[1]);
}
};总结
打家劫舍题型I,II,III，逐一增加难度。第三题也是树形DP的入门题目，通过本题也能够了解树形DP就是在树上进行递归公式的推导。相较于此前我们使用的一维dp数组和二维dp数组还是有很大去别的，需要理解并反复练习。同时我们在第三题中还是用到了记忆化搜索的方式，实际上记忆化搜索也是实现动态规划的方式之一，其与正常的动态规划的方法的区别在于：原文链接
记忆化搜索：「自顶向下」的解决问题，采用自然的递归方式编写过程，在过程中会保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
-
优点：代码清晰易懂，可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的，使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题，通过递归调用来解决。
-
缺点：可能会因为递归深度过大而导致栈溢出问题。
递推：「自底向上」的解决问题，采用循环的方式编写过程，在过程中通过保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
-
优点：避免了深度过大问题，不存在栈溢出问题。计算顺序比较明确，易于实现。
-
缺点：无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂，如果使用递推方法来计算，就会导致代码实现变得非常困难。
