企业网站建设费用大约多少钱,中国it企业排行榜,网站建设课程性质,网站如何做中英文双语言版本代码随想录训练营Day48 | Leetcode 198、213、337 一、198 打家劫舍二、213 打家劫舍II三、337 打家劫舍III 一、198 打家劫舍
题目链接#xff1a;198 打家劫舍
核心#xff1a;经典的动态规划问题#xff0c;是否选择当前房屋有两种状态#xff0c;要么选#xff0c;要… 代码随想录训练营Day48 | Leetcode 198、213、337 一、198 打家劫舍二、213 打家劫舍II三、337 打家劫舍III 一、198 打家劫舍
题目链接198 打家劫舍
核心经典的动态规划问题是否选择当前房屋有两种状态要么选要么不选 如果选择当前房屋那么考虑选择前两个房屋隐含前一个房屋必然不能选 如果不选当前房屋那么考虑选择前一个房屋 究竟是选择还是不选择由两种情况的max决定。 由于当前值的状态依赖于前一个和前两个值因此初始化时需初始化前两个dp数组值。 int rob(vectorint nums) {//是否选择当前房屋依赖于前一个或者前两个房屋的状态if(nums.size()0) return 0;if(nums.size()1) return nums[0];vectorint dp(nums.size(),0);dp[0]nums[0]; //初始化dp[1]max(nums[0],nums[1]);for(int i2;inums.size();i)dp[i]max(dp[i-1],dp[i-2]nums[i]);return dp[nums.size()-1];}二、213 打家劫舍II
题目链接213 打家劫舍II
核心在198 打家劫舍的基础上增加了一个条件首尾不能同时选择可将这个数组分成三种情况其一不选首尾其二不选首元素其三不选尾元素而后两种情况涵盖了第一种情况因此只需考虑后两种情况。 第一不选首元素即考虑除了首元素之外的其他数组元素的选择情况得到此时的max 第二不选尾元素即考虑除了尾元素之外的其他数组元素的选择情况得到此时的max 最后比较两种情况取其最大值max即为没有同时取首尾元素的最大值。 int robBase(vectorint nums,int start,int end){//基础的打家劫舍函数if(endstart)return nums[start];vectorint dp(nums.size(),0);dp[start]nums[start]; //前两个元素的初始化dp[start1]max(nums[start],nums[start1]);for(int istart2;iend;i)dp[i]max(dp[i-1],dp[i-2]nums[i]);return dp[end];}int rob(vectorint nums) {//首尾相连说明选了第一个不能选最后一个故存在两种情况其一忽略尾元素其二忽略头元素取其maxif(nums.size()0) return 0;if(nums.size()1) return nums[0];int res1robBase(nums,0,nums.size()-2); //不包括尾元素int res2robBase(nums,1,nums.size()-1); //不包括头元素return max(res1,res2);}三、337 打家劫舍III
题目链接337 打家劫舍III
核心二叉树的动态规划问题即在二叉树遍历中融入动态规划。首先明确此二叉树的遍历顺序必须是后序遍历左右中因为需要参考左右子树的返回值对【中】进行处理。 递归三部曲 第一确定递归函数的参数和返回值参数即当前节点返回值是当前节点选与不选的两种状态下的金额故返回值是一个长度为2的数组就是dp数组dp[0]表示不选该节点的金额dp[1]表示选择该节点的金额 第二确定终止条件当前节点为空时无论选与不选金额都是0因此返回{0,0}这其实是dp数组的初始化 第三确定遍历顺序后序遍历左右中 第四确定单层递归的逻辑实质是对【中】的处理如果不选该节点那么左右孩子都可以考虑选也可能不选由max决定需要取其最大值如果选择该节点那么左右孩子都不能选这不存在考虑只能是不选。 最后遍历整棵树返回的是头节点的两种状态下的金额取其max即可。 vectorint robTree(TreeNode* cur){//树的dp返回值即dp数组dp[0]:不选择cur的最大金额dp[1]:选择cur的最大金额//1.终止条件即dp数组的初始化if(curnullptr)return {0,0}; //2.遍历顺序后序遍历--左右中vectorint leftrobTree(cur-left);vectorint rightrobTree(cur-right);//3.单层逻辑处理即中的处理int val1max(left[0],left[1])max(right[0],right[1]); //不选择cur左右孩子可以选int val2cur-valleft[0]right[0]; //选择cur要求左右孩子均不能选return {val1,val2}; //最终返回的是头节点的dp数组}int rob(TreeNode* root) {vectorint resrobTree(root);return max(res[0],res[1]);}
