平台网站可以做第三方检测报告,大数据营销优势,软件开发流程流程图,什么叫个人网站软件提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 一、198打家劫舍二、213打家劫舍II三、337打家劫舍III 一、198打家劫舍
class Solution {
public:int rob(vectorint nums) {vectorint dp(n… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 一、198打家劫舍二、213打家劫舍II三、337打家劫舍III 一、198打家劫舍
class Solution {
public:int rob(vectorint nums) {vectorint dp(nums.size() 2, 0);for (int i 0; i nums.size(); i ) {dp[i2] max(dp[i1], dp[i] nums[i]);}return dp[nums.size()1];}
};二、213打家劫舍II
class Solution {
public:int helper(vectorint nums, int start, int end) {vectorint dp(2, 0);for (int i start; i end; i ) {dp.push_back(max(dp.back(), dp[dp.size()-2] nums[i]));}return dp.back();}int rob(vectorint nums) {if (nums.size() 1) {return nums.back();}int res1 helper(nums, 0, nums.size() - 1);int res2 helper(nums, 1, nums.size());return max(res1, res2);}
};三、337打家劫舍III
class Solution {
public:unordered_mapTreeNode*, 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); }
};优化版
class Solution {
public:vectorint robTree(TreeNode* cur) {if (cur nullptr) {return vectorint(2, 0);}vectorint left robTree(cur-left);vectorint right robTree(cur-right);//偷当前节点,左右孩子不能偷int val1 cur-val left[1] right[1];//不偷当前节点左右孩子可以偷int val2 max(left[0], left[1]) max(right[0], right[1]);return {val1, val2};}int rob(TreeNode* root) {vectorint dp robTree(root);return max(dp[0], dp[1]);}
};
