遂宁网站建设哪家好,找人做网站被骗,wordpress 商城系统,那个网站可以做双色球号码对比的198. 打家劫舍 我们从第一个开始分析#xff1a;
dp[i]:i表示索引#xff0c;dp表示当前索引可以拿到的最高金额
索引为0时#xff0c;可以拿到的最高金额为1#xff1b;
索引为1时#xff0c;可以拿到的最高金额就是在索引[0,1]之间取#xff0c;为2
索引为2时…198. 打家劫舍 我们从第一个开始分析
dp[i]:i表示索引dp表示当前索引可以拿到的最高金额
索引为0时可以拿到的最高金额为1
索引为1时可以拿到的最高金额就是在索引[0,1]之间取为2
索引为2时就要看前两个索引[0,1]的状态了如果索引0被取那么当前值就可取如果索引1被取当前值就不能取。所以索引2可得的最高金额为max(dp[2-1],dp[2-2]nums[i]) 往下推就可以发现当前索引可以拿到的最高金额与前两个索引的状态有关得递推公式dp[i]max(dp[i-1],dp[i-2]nums[i])
class Solution {
public:int rob(vectorint nums) {if(nums.size()2) return nums[0];vectorint pd(nums.size(),0);pd[0]nums[0];pd[1]max(nums[0],nums[1]);for(int i2;inums.size();i){pd[i]max(pd[i-1],pd[i-2]nums[i]);}return pd[nums.size()-1];}
};
213. 打家劫舍 II 环形房间的问题就在于不能同时取首尾两个房间所以要分情况。
1.不偷第一个房间
2.不偷最后一个房间
class Solution {
public:int rob(vectorint nums) {if(nums.size()2) return nums[0];else if(nums.size()2) return max(nums[0],nums[1]);vectorint pd(nums.size(),0);//不偷窃第一个房间pd[1]nums[1];pd[2]max(nums[1],nums[2]);for(int i3;inums.size();i){pd[i]max(pd[i-1],pd[i-2]nums[i]);}int noOnepd[nums.size()-1];//不偷窃最后一个房间pd.clear();pd[0]nums[0];pd[1]max(nums[1],nums[0]);for(int i2;inums.size()-1;i){pd[i]max(pd[i-1],pd[i-2]nums[i]);}int noEndpd[nums.size()-2];return max(noOne,noEnd);}
};
337. 打家劫舍 III 这题需要递归与动态规划同时进行看到树要首先试试递归遍历。最初我使用层序遍历的结果发现只能以一层为单位进行操作不够灵活不能通过全部测试。这里每个结点都只有两种状态那就是偷与不偷用一个数组来记录偷与不偷所能取得的最高金额。需采用后续遍历因为我们要知道当前结点的子树所取最高金额的情况。
class Solution {
public:vectorint robTree(TreeNode* root){if(rootnullptr) return {0,0};//存储左子树偷与不偷能够得到的最大金额vectorint leftrobTree(root-left);//存储右子树偷与不偷能够得到的最大金额vectorint rightrobTree(root-right);//偷当前结点int val0root-valleft[1]right[1];//不偷当前结点int val1max(left[0],left[1])max(right[0],right[1]);return {val0,val1};}int rob(TreeNode* root) {vectorint ansrobTree(root);return max(ans[0],ans[1]);}
};
