八冶建设集团有限公司网站,网站建设教程简笔画,信息管理网站开发实验体会,wordpress 更新页面打家劫舍
题目#xff1a;198.打家劫舍 213.打家劫舍II 337.打家劫舍III
需要重做#xff1a;全部 198.打家劫舍 思路#xff1a;第i个房子偷与不偷#xff0c;取决于第i-2个房子和第i-1个房子 注意#xff1a;注意下标的一致性。现在的下标含义是房子的下标#x…打家劫舍
题目198.打家劫舍 213.打家劫舍II 337.打家劫舍III
需要重做全部 198.打家劫舍 思路第i个房子偷与不偷取决于第i-2个房子和第i-1个房子 注意注意下标的一致性。现在的下标含义是房子的下标而不是第几个房子。也可以更改 五部 1.dp[i]:在第i个房子时最多的钱 2.dp[i]max(dp[i-2]nums[i],dp[i-1]); 3.由递推式知道要初始化dp0和dp1 4.从前到后遍历。 代码 class Solution {
public:int rob(vectorint nums) {int nnums.size();if(n1)return nums[0];if(n2)return max(nums[0],nums[1]);vectorintdp(n,0);dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(int i2;in;i){dp[i]max(dp[i-1],dp[i-2]nums[i]);}return dp[n-1];}
}; 213.打家劫舍II 思路在上题基础上增加了环形。所以分成三种情况 1.不含首尾元素 2.可能包含首元素不含尾元素 3.可能包含尾元素不含首元素 利用198的函数即可 注意其中情况2 和情况3 都包含了情况1所以情况1在计算中可以忽略 代码 class Solution {
public:int rob(vectorint nums) {int nnums.size();if(n1)return nums[0];if(n2)return max(nums[0],nums[1]);int res1robhomes(nums,0,n-2);int res2robhomes(nums,1,n-1);return max(res1,res2);}int robhomes(vectorintnums,int start,int end){int nend-start1;if(n1)return nums[start];if(n2)return max(nums[start],nums[start1]);vectorintdp(n,0);dp[0]nums[start];dp[1]max(nums[start],nums[start1]);for(int i2;in;i){dp[i]max(dp[i-1],dp[i-2]nums[starti]);}return dp[n-1];}
}; 337.打家劫舍III --树形dp 思路就是从树根节点出发决定每个节点是偷还是不偷。结合了树的遍历和动规。因为需要左右 的值来决定中间的值所以选择后序遍历。 注意 树的分析 1.参数返回值应该return一个两个元素的数组分别代表偷当前节点和不偷当前节点的值。参数为树节点 2.终止条件遇到空节点return00遇到叶子返回叶子val0 3.遍历顺序后序遍历因为需要左右的值。且需要记录左右的值 vectorintleftrob(root-left) 4.单层逻辑val1cur-valleft(1)right(1)偷该节点 val2max(left[0],left[1])max(right[0].right[1]);不偷该节点可以选择左右孩子偷还是不偷选最大 的 最后returnval1val2 代码 class Solution {
public:int rob(TreeNode* root) {vectorintresrobTree(root);return max(res[0],res[1]);}vectorintrobTree(TreeNode*cur){if(curnullptr)return {0,0};//(偷该节点不偷该节点)if(cur-leftnullptrcur-rightnullptr)return{cur-val,0};vectorintleftrobTree(cur-left);vectorintrightrobTree(cur-right);int val1cur-valleft[1]right[1];int val2max(left[0],left[1])max(right[0],right[1]);return {val1,val2};}
};
