今天是打家劫舍系列,难度从前往后递增,只有第1道自己做出来了。第2、3道都是将DP作为解法的一部分,都有难度,尤其是第3题。第2道题要计算两个dp数组,再从中取较大值。第3道题有2种解法。第1种解法回顾了记忆化递归;第2种解法则是初次接触树形DP,将当前节点的dp数组作为返回值返回,供上一层的递归函数判断处理。
之前遇到过,这次自己解决了。dp[i]定义为从前i家房屋能获取的金额。状态转移方程方面,对于第2家房屋,只有打劫或不打劫两个选项。如果不打劫的话,就取上一个值dp[i - 1];而如果打劫的话,就意味着上一个房屋不在考虑范围内,所以要取上“上一个房屋对应的dp值”与“当前房屋价值”的和,即dp[i - 2] + nums[i]。目标是获取尽可能多的金额,所以从两者中取较大值,对应状态转移方程为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。初始化方面,对于前0个房屋,最优选择就是打劫第0个房屋,所以设置dp[0]为nums[0];对于前1个房屋,应该打劫第0、第1个房屋中价值较大的,所以设置为max(dp[0], dp[1])。每个点的值都依赖于其左方的2个值,所以从左向右遍历。
- class Solution {
- public:
- int rob(vector<int>& nums) {
- if (nums.size() == 1) {
- return nums[0];
- }
- vector<int> dp(nums.size());
- dp[0] = nums[0];
- dp[1] = max(nums[0], nums[1]);
- for (int i = 2; i < nums.size(); ++i) {
- dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
- }
- return dp.back();
- }
- };
这一题的重点是dp[i]仅对应将第i个房屋考虑在内,而不一定会打劫第i个房屋,具体是否由状态转移方程来计算。
二刷:dp数组不需要两行分别对应打劫了和没打劫,只需要一行即可。
自己没做出来。这道题相比上一题,只增加了一个限制条件,就是房屋变成了环形排列,所以首尾房屋不能都打劫。那么就有两种选择,要么不考虑第一间房屋,要么不考虑最后一间房屋。然后再各自用上一题的解法得到结果,取两者的最大值作为最终答案。具体实现方法可以将上一题的方法抽象为函数,将数组的起始、末尾下标作为函数参数。
- class Solution {
- public:
- int robRange(vector<int>& nums, int indBegin, int indEnd) {
- if (indEnd == indBegin) {
- return nums[indBegin];
- }
- int len = indEnd - indBegin + 1;
- vector<int> dp(len);
- dp[0] = nums[indBegin];
- dp[1] = max(nums[indBegin], nums[indBegin + 1]);
- for (int i = 2; i < len; ++i) {
- dp[i] = max(dp[i - 1], dp[i - 2] + nums[indBegin + i]); // 不是nums[i]
- }
- return dp[len - 1];
- }
- int rob(vector<int>& nums) {
- if (nums.size() == 1) {
- return nums[0];
- }
- int ansFront = robRange(nums, 0, nums.size() - 2);
- int ansBack = robRange(nums, 1, nums.size() - 1);
- return max(ansFront, ansBack);
- }
- };
函数的实现需要注意下标范围,比如第12行要注意nums和dp下标并不统一。题解的实现方法则是将dp数组大小设置为与nums一样,从而使得下标统一,不容易出错,虽然会多占用一个没用的int空间。具体实现是用下面的代码替换上面的第7~13行。
- vector<int> dp(nums.size());
- dp[indBegin] = nums[indBegin];
- dp[indBegin + 1] = max(nums[indBegin], nums[indBegin + 1]);
- for (int i = indBegin + 2; i <= indEnd; ++i) {
- dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
- }
- return dp[indEnd];
二刷:忘记方法。 忘记对输入nums长度为1或2的判断。
比较难,自己没想出来,题解有两种方法。第1种是递归解法。因为需要当前节点的“子树”或“孙子树”的返回值来决定当前节点的返回值,所以采用后序遍历。对于这道题,同样分为打劫当前点,和不打劫当前点两种情况。
如果打劫当前节点,那么当前点的左右子节点就都不能被打劫了。所以应该考虑当前节点的孙子子树,也就是当前节点的“左子节点的左右子节点、右子节点的左右子节点”,这4个节点作为根节点的4棵树。将这4颗子树的返回值加起来,再加上当前节点的val,就得到打劫当前点所得到的金额。
而如果不打劫当前节点,就应该考虑当前节点的左右子树,将两者的返回值相加作为结果。然后将这两种情况各自的结果取最大值,即是当前节点的返回值。
递归的出口应该设置为遇到空节点就返回0。而为了减少不必要的递归,可以把叶子节点也设置为出口,返回叶子节点的val。而为了避免空指针问题,对于打劫当前节点的选择,在访问其孙子节点时,要保证其左或右子节点存在才能进行递归。
在打劫当前节点的部分,已经对孙子节点进行了递归。但在不打劫当前节点部分,递归孩子节点的内部还会对孙子节点进行重复递归,所以直接用上面的方法会导致超时。解决方法是用day 46中第1题(LeetCode 139. 单词拆分)首次接触到的而记忆化递归。具体做法是设立一个map,用于存储每个节点的返回值。每次进入递归函数,都查询一下当前节点是否已经有了相应的返回值在map中。如果已经有了,就直接返回该值。没有的话,才进行分情况的递归,并在得到结果后将其放入map中。
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- public:
- unordered_map
int> umap; - int rob(TreeNode* root) {
- if (root == nullptr) {
- return 0;
- }
- if (root->left == nullptr && root->right == nullptr) { // 可不写,但会多一层递归
- return root->val;
- }
- if (umap[root]) {
- return umap[root];
- }
- // 打劫当前节点,并考虑当前节点的孙子子树
- int val1 = root->val;
- if (root->left) {
- val1 += rob(root->left->left) + rob(root->left->right);
- }
- if (root->right) {
- val1 += rob(root->right->left) + rob(root->right->right);
- }
- // 不打劫当前节点,并考虑当前节点的左右子树
- int val2 = rob(root->left) + rob(root->right);
- umap[root] = max(val1, val2);
- return max(val1, val2);
- }
- };
第2种解法是树形DP解法。首先定义方面,将dp[0]和dp[1]分别定义为不打劫、和打劫某个节点,从“该节点作为根节点的树”中所能得到的金额。也就是说dp数组的总长度就是2,将dp数组作为递归函数的返回值。由于需要左右子节点各自打劫与不打劫的总共4个返回值,才能决定当前节点的两种情况对应的2个返回值,所以仍然需要后序遍历。递归出口方面,仍然是空结点返回0,因为空节点打劫与不打劫的金额都是0。
而对于其他节点,在得到了左子树的返回值dpLeft和右子树的返回值dpRight后,就可以分不打劫、和打劫当前节点的两种情况来讨论。如果不打劫当前节点,那么其左右子结点是否被打劫就没有限制,取各自返回值的最大值再相加就可以,对应max(resLeft[0], resLeft[1]) + max(resRight[0], resRight[1])。而如果打劫当前节点,那么其左右子节点都不能被打劫,只能选择各自dp的第0位,再加上当前节点的val,对应cur->val + dpLeft[0] + dpRight[0]。
得到这两种情况对应的结果后,再将两者作为返回值返回。然后在主函数中,取根节点返回值中两个数的较大值作为最终结果。
- class Solution {
- public:
- // vector
第0、1位分别代表不打劫、打劫当前节点 - vector<int> robTree(TreeNode* cur) {
- if (cur == nullptr) {
- return {0, 0};
- }
- vector<int> dpLeft = robTree(cur->left);
- vector<int> dpRight = robTree(cur->right);
- int valNo = max(dpLeft[0], dpLeft[1]) + max(dpRight[0], dpRight[1]);
- int valYes = cur->val + dpLeft[0] + dpRight[0];
- return {valNo, valYes};
- }
- int rob(TreeNode* root) {
- vector<int> res = robTree(root);
- return max(res[0], res[1]);
- }
- };
二刷:忘记方法。