企业官网建设流程全解析

沈阳响应式网站建设,长安做网站公司,WordPress表单支付插件,建一个com网站要多少钱代码随想录算法训练营第三十四天任务198.打家劫舍213.打家劫舍II337.打家劫舍III198.打家劫舍 题目链接#xff1a;198.打家劫舍 递归五步曲分析#xff1a; 确定dp数组下标及其含义 dp[i]: 表示在[0~i]之间的房间进行偷窃的最高金额为dp[i]确定递推公式 偷盗当前房屋 i : …代码随想录算法训练营第三十四天任务198.打家劫舍213.打家劫舍II337.打家劫舍III198.打家劫舍题目链接198.打家劫舍递归五步曲分析确定dp数组下标及其含义dp[i]: 表示在[0~i]之间的房间进行偷窃的最高金额为dp[i]确定递推公式偷盗当前房屋 i : dp[i - 2] nums[i]不偷当前房屋 i : dp[i - 1]取最高金额所以递推公式为dp[i] max(dp[i - 1], dp[i - 2] nums[i])初始化dp[0] nums[0];dp[1] max(nums[0], nums[1])确定遍历顺序从前面房前是否被偷来确定时候偷后面的房间所以遍历顺序是从前往后的。举例推倒classSolution{public:introb(vectorintnums){if(nums.size()1)returnnums[0];vectorintdp(nums.size(),0);dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(inti2;inums.size();i){dp[i]max(dp[i-1],dp[i-2]nums[i]);}returndp[nums.size()-1];}};时间复杂度O(n)空间复杂度O(n)213.打家劫舍II题目链接213.打家劫舍II首尾任选其一。房间首尾相连只包含首元素不包含尾元素和只包含尾元素不包含首元素两种情况取最大值。这道题看题解了我对问题的拆分能力还待提升。classSolution{private:introbRange(vectorintnums,intstart,intend){// 左闭右闭区间if(startend)returnnums[start];vectorintdp(nums.size(),0);dp[start]nums[start];dp[start1]max(nums[start],nums[start1]);for(intistart2;iend;i){dp[i]max(dp[i-1],dp[i-2]nums[i]);}returndp[end];}public:introb(vectorintnums){if(nums.size()1)returnnums[0];intresult1robRange(nums,0,nums.size()-2);// 包含首元素不包含尾元素intresult2robRange(nums,1,nums.size()-1);// 不包含首元素包含尾元素returnmax(result1,result2);}};时间复杂度O(n)空间复杂度O(n)337.打家劫舍III题目链接337.打家劫舍IIIdp数组在树形结构上进项状态转移秒啊递归三步曲动规五步曲确定递归函数的参数和返回值 (及dp数组含义)每个节点有 偷与不偷 两种状态所获得的金钱。用一个长度为2的dp数组表示。dp[0]表示不偷该节点获得的最大金额。dp[1]表示 偷 该节点获得的最大金额。所以递归参数是节点递归返回值是一个长度为2的数组。vectorintrobTree(TreeNode*cur)确定终止条件 dp初始化如果是空节点偷 与 不偷 金额都为0.if(curnullptr)returnvectorint{0,0};确定遍历顺序需要通过递归返回值来进行下一步的计算所以采用后序遍历。递归左节点递归右节点确定当前节点的递归逻辑 (dp递推公式)如果偷当前节点其左右孩子就不能偷, 最大金额为val1 cur-val left[0] right[0]left[0]表示不偷左孩子的最大金额right[0]表示不偷右孩子的最大金额如果不偷当前节点左右孩子就可以偷最大金额为左右孩子偷 或 不偷的最大金额val2 max(left[0], left[1]) max(right[0], right[1])当前节点的状态为{val2, val1}举例推导classSolution{private:// dp[0]:不偷 dp[1]:偷vectorinttraversal(TreeNode*cur){if(curnullptr)return{0,0};vectorintlefttraversal(cur-left);vectorintrighttraversal(cur-right);intval1cur-valleft[0]right[0];// 偷当前节点intval2max(left[0],left[1])max(right[0],right[1]);// 不偷当前节点return{val2,val1};}public:introb(TreeNode*root){vectorintresulttraversal(root);returnmax(result[0],result[1]);}};时间复杂度O(n)空间复杂度O(log n)