代码随想录算法训练营第四十一天|leetcode198、213、337题

一、leetcode第198题

本题设置dp数组，dp[i]的含义是长度在0-i的房间内可偷得的最大金额，故递推公式为dp[i]=max(dp[i-1],dp[i-2]+nums[i])。

具体代码如下：

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

二、leetcode第213题

本题与上题类似，需要将房子排成环，因此需要区分取nums[0]和取nums[nums.size()-1]两种情况，在这两种情况下取最大值。

具体代码如下：

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

三、leetcode第337题

本题将房子设置成了二叉树的结构，需要将树的遍历与动态规划相结合，对每个结点设置一个dp数组存取两个值，即偷该结点的最大金额和不偷该结点的最大金额，因此需要后序遍历将每个结点的dp数组的值进行相加，最后返回到根结点。

具体代码如下：

class Solution {
public:
    int rob(TreeNode* root) {
    vector<int>dp=getarray(root);
    return max(dp[0],dp[1]);
    }
    vector<int>getarray(TreeNode*root)
    {
        if(root==NULL)
        {
            return vector<int>{0,0};
        }
        vector<int>lchild=getarray(root->left);
        vector<int>rchild=getarray(root->right);
        int var1=root->val+lchild[0]+rchild[0];
        int var2=max(lchild[0],lchild[1])+max(rchild[0],rchild[1]);
        return{var2,var1};
    }
};