力扣刷题记录（20）LeetCode：198、213、337

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(vector<int>& nums) {
        if(nums.size()<2)   return nums[0];
        vector<int> pd(nums.size(),0);
        pd[0]=nums[0];
        pd[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.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(vector<int>& nums) {
        if(nums.size()<2)   return nums[0];
        else if(nums.size()==2) return max(nums[0],nums[1]);
        vector<int> pd(nums.size(),0);
        //不偷窃第一个房间
        pd[1]=nums[1];
        pd[2]=max(nums[1],nums[2]);
        for(int i=3;i<nums.size();i++)
        {
            pd[i]=max(pd[i-1],pd[i-2]+nums[i]);
        }
        int noOne=pd[nums.size()-1];
        //不偷窃最后一个房间
        pd.clear();
        pd[0]=nums[0];
        pd[1]=max(nums[1],nums[0]);
        for(int i=2;i<nums.size()-1;i++)
        {
            pd[i]=max(pd[i-1],pd[i-2]+nums[i]);
        }
        int noEnd=pd[nums.size()-2];
        return max(noOne,noEnd);
    }
};

337. 打家劫舍 III

这题需要递归与动态规划同时进行，看到树要首先试试递归遍历。最初我使用层序遍历的，结果发现只能以一层为单位进行操作，不够灵活，不能通过全部测试。这里每个结点都只有两种状态，那就是偷与不偷，用一个数组来记录偷与不偷所能取得的最高金额。需采用后续遍历，因为我们要知道当前结点的子树所取最高金额的情况。 

class Solution {
public:
    vector<int> robTree(TreeNode* root)
    {
        if(root==nullptr)   return {0,0};
        //存储左子树偷与不偷能够得到的最大金额
        vector<int> left=robTree(root->left);
        //存储右子树偷与不偷能够得到的最大金额
        vector<int> right=robTree(root->right);
        //偷当前结点
        int val0=root->val+left[1]+right[1];
        //不偷当前结点
        int val1=max(left[0],left[1])+max(right[0],right[1]);
        return {val0,val1};
    }
    int rob(TreeNode* root) {
        vector<int> ans=robTree(root);
        return max(ans[0],ans[1]);
    }
};