【Day34 LeetCode】动态规划DP Ⅶ 打家劫舍

一、动态规划DP Ⅶ 打家劫舍

1、leetcode.cn/problems/house-robber/" rel="nofollow">打家劫舍198

首先确定dp数组，dp[i]表示从0~i房间最大可以获得的金额数
然后确定dp方程，对于当前房间i，dp[i]取决于偷不偷当前房间，如果偷当前房间，则前一个房间不能包括，如果不偷当前房间，就可以包括前一个房间。dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1);dp[1] = nums[0];for(int i=2; i<=n; ++i)dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);return dp[n];}
};

从递推公式发现dp[i]只与前面两个数字有关，因此可以不采用数组而是采用两个变量来不断更新结果，优化空间复杂度，代码如下：

class Solution {
public:int rob(vector<int>& nums) {int pre = 0, cur = nums[0];for(int i=1; i<nums.size(); ++i){int tmp = cur;cur = max(cur, pre + nums[i]);pre = tmp;}return cur;}
};

2、leetcode.cn/problems/house-robber-ii/description/" rel="nofollow">打家劫舍Ⅱ 213

这题在上一题的基础上变成了环，很容易陷入首尾相邻的困局中。这题比较巧妙，直接忽略头部元素或者首部元素，从而破除了环，采用上一题非环的求解结果，取两者最大值即可。

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if(n==1)return nums[0];return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1));}int robRange(vector<int>& nums, int left, int right){int pre = 0, cur = nums[left];for(int i=left+1; i<=right; ++i){int tmp = cur;cur = max(cur, pre + nums[i]);pre = tmp;}return cur;}
};

3、leetcode.cn/problems/house-robber-iii/description/" rel="nofollow">打家劫舍Ⅲ 337

这题的数据结构变成了二叉树。关于二叉树，最先要明确的就是二叉树的遍历，由于入口是根节点，所以应该是前序遍历。
暴力递归的代码如下，会超时，因为有重复计算的结果

/*** 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:int rob(TreeNode* root) {if(root==nullptr)return 0;if(root->left==nullptr && root->right==nullptr)return root->val;int v1 = root->val; // 选择当前节点if(root->left)v1 += rob(root->left->left) + rob(root->left->right);if(root->right)v1 += rob(root->right->left) + rob(root->right->right);int v2 = rob(root->left) + rob(root->right); // 不选当前节点return max(v1, v2);}
};

在此基础上添加一个记忆化搜索

/*** 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 {unordered_map<TreeNode*, int> mp;
public:int rob(TreeNode* root) {if(root==nullptr)return 0;if(root->left==nullptr && root->right==nullptr)return root->val;if(mp[root])return mp[root];int v1 = root->val; // 选择当前节点if(root->left)v1 += rob(root->left->left) + rob(root->left->right);if(root->right)v1 += rob(root->right->left) + rob(root->right->right);int v2 = rob(root->left) + rob(root->right); // 不选当前节点v1 = max(v1, v2);mp[root] = v1;return v1;}
};

采用动态规划的思想，对于一个节点，有偷与不偷两个状态

/*** 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 {vector<int> robTree(TreeNode* node){if(node==nullptr)   return vector<int>{0, 0};vector<int> left = robTree(node->left);vector<int> right = robTree(node->right);// 不偷当前节点int v1 = max(left[0], left[1]) + max(right[0], right[1]);// 偷当前节点int v2 = node->val + left[0] + right[0];return {v1, v2};}
public:int rob(TreeNode* root) {vector<int> ans = robTree(root);return max(ans[0], ans[1]);}
};