【代码随想录】刷题Day47

这篇具有很好参考价值的文章主要介绍了【代码随想录】刷题Day47。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.打家劫舍

198. 打家劫舍

1.dp数组含义：dp[i]为i位置下的最大能得到的价值

2.根据条件：相邻不能偷。i位置的最大价值取决于i-1位置是否已经偷过了。如果偷过了，i位置的最大价值就是dp[i-1]，即i位置的物品不偷；如果没有偷过，i位置的最大价值就是dp[i-2]+nuvms[i]，i位置的数和对应的dp[i-2]

3.特别注意的，由于nuvms数组从0就开始了，但是我下面写的代码dp[0]=0，表示0位置不需要偷东西，那么此时所有的i的位置判断都要做出相对的变换，下列条件变化：dp[i]=max(dp[i-2]+nuvms[i-1],dp[i-1])和dp[1]=nuvms[0];

class Solution {
public:
    int rob(vector<int>& nuvms) {
        if (nuvms.size() == 0)
            return 0;
        if (nuvms.size() == 1)
            return nuvms[0];
        vector<int> dp(nuvms.size()+1,0);
        dp[0]=0;
        dp[1]=nuvms[0];
        for(int i=2;i<=nuvms.size();i++)
        {
            dp[i]=max(dp[i-2]+nuvms[i-1],dp[i-1]);
        }
        return dp[nuvms.size()];
    }
};

2.打家劫舍 II

213. 打家劫舍 II

1.与上一题不同的是，本题的判断加入了房屋围成一圈，也就是说，末尾和开头是连在一起的。条件就苛刻起来了，最后一个位置还需要考虑第一个位置是否被打劫过

2.dp数组的含义与之前一致，表示dp[i]为i位置下的最大能得到的价值

3.由于首尾相连，我们不能直接使用上面做过的方法。但是我们可以拆分出来，我们其实可以将整个遍历看为两次遍历。第一次是只遍历首不遍历尾，第二次是只遍历尾不遍历首。之所以这样是因为dp数组的定义：最大能得到的价值。也就是说，在单次的遍历中，我们不需要考虑某个具体位置是否会被考虑进去，因为条件函数已经帮我们判断了

4.因此，我们只需要将两次的dp数组结果取出最大的即可。那么为了解耦，设计一个函数，传入的为第一个值和第二个值位置，dp数组的第一个和第二个分别对应第一个值和第二个值位置。最后的条件也变为了：dp[i]=max(dp[i-2]+nums[i+num0],dp[i-1]);

class Solution {
public:
    int Getnum(vector<int>& nums,int num0, int num1)
    {
        vector<int> dp(nums.size()-1,0);
        dp[0]=nums[num0];
        dp[1]=max(nums[num0],nums[num1]);
        for(int i=2;i<nums.size()-1;i++)
        {
            dp[i]=max(dp[i-2]+nums[i+num0],dp[i-1]);
        }
        return dp[nums.size()-2];
    }

    int rob(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        if(nums.size()==1)
            return nums[0];
        if(nums.size()==2)
            return max(nums[0],nums[1]);
        int dp1 = Getnum(nums,0,1);
        int dp2 = Getnum(nums,1,2);
        return max(dp1,dp2);
    }
};

3.打家劫舍 III

337. 打家劫舍 III

1.本题需要树形dp，每层有两个数，一个数表示没偷当前位置的最大价值；一个数表示偷当前位置的最大价值。分别存在vector<int>dp的dp[0]和dp[1]中

2.首先我们要清楚，遍历顺序应该为后序遍历，因为所谓的最大价值不能从上到下进行遍历，其约束条件会越来越苛刻。我们从下往上能使得条件只考虑在两层之间。

3.如果root==nullptr，此时没有东西给我们打劫，那么直接返回偷与不偷都为0的vector<int>{0,0};

4.先处理中间条件：如果该层偷，那么下面的两层都不能偷，对应的我们最大价值为当前加上左右两边都不偷的最大价值root->val+left[0]+right[0]；如果该层不偷，那么我们要取左右两边的最大值max(left[0],left[1])+max(right[0],right[1])。这样得到dp[0]和dp[1]为当前层的最大价值的两种情况，return vector<int>{val2,val1}。

5.左右遍历其实就是创造数组接住下面传上来的偷与不偷的最大价值情况。vector<int> left = robTree(root->left)，vector<int> right = robTree(root->right);文章来源地址https://www.toymoban.com/news/detail-472206.html

class Solution {
public:
    vector<int> robTree(TreeNode* root)
    {
        if(root==nullptr)
            return vector<int>{0,0};
        vector<int> left = robTree(root->left);
        vector<int> right = robTree(root->right);
        int val1 = root->val+left[0]+right[0];
        int val2 = max(left[0],left[1])+max(right[0],right[1]);
        return vector<int>{val2,val1};
    }
    int rob(TreeNode* root) {
        vector<int> dp = robTree(root);
        return max(dp[0],dp[1]);
    }
};

到了这里，关于【代码随想录】刷题Day47的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！