【C++编程能力提升】

一、198 打家劫舍

题目链接：198 打家劫舍

核心：经典的动态规划问题，是否选择当前房屋有两种状态，要么选，要么不选；
如果选择当前房屋，那么考虑选择前两个房屋（隐含前一个房屋必然不能选）；
如果不选当前房屋，那么考虑选择前一个房屋；
究竟是选择还是不选择，由两种情况的max决定。
由于当前值的状态依赖于前一个和前两个值，因此初始化时需初始化前两个dp数组值。

    int rob(vector<int>& nums) {
        //是否选择当前房屋，依赖于前一个或者前两个房屋的状态
        if(nums.size()==0)  return 0;
        if(nums.size()==1)  return nums[0];
        vector<int> dp(nums.size(),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];
    }
1
2
3
4
5
6
7
8
9
10
11

二、213 打家劫舍II

题目链接：213 打家劫舍II

核心：在198 打家劫舍的基础上，增加了一个条件，首尾不能同时选择，可将这个数组分成三种情况，其一不选首尾，其二不选首元素，其三不选尾元素，而后两种情况涵盖了第一种情况，因此只需考虑后两种情况。
第一，不选首元素，即考虑除了首元素之外的其他数组元素的选择情况，得到此时的max；
第二，不选尾元素，即考虑除了尾元素之外的其他数组元素的选择情况，得到此时的max；
最后比较两种情况，取其最大值max即为没有同时取首尾元素的最大值。

    int robBase(vector<int>& nums,int start,int end)
    {//基础的打家劫舍函数
        if(end==start)
            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-1],dp[i-2]+nums[i]);
        return dp[end];
    }
    int rob(vector<int>& nums) {
    //首尾相连说明选了第一个不能选最后一个，故存在两种情况：其一忽略尾元素，其二忽略头元素，取其max
        if(nums.size()==0)  return 0;
        if(nums.size()==1)  return nums[0];
        int res1=robBase(nums,0,nums.size()-2); //不包括尾元素
        int res2=robBase(nums,1,nums.size()-1); //不包括头元素
        return max(res1,res2);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、337 打家劫舍III

题目链接：337 打家劫舍III

核心：二叉树的动态规划问题，即在二叉树遍历中融入动态规划。首先明确此二叉树的遍历顺序必须是后序遍历（左右中），因为需要参考左右子树的返回值对【中】进行处理。
（递归三部曲）
第一，确定递归函数的参数和返回值：参数即当前节点，返回值是当前节点选与不选的两种状态下的金额，故返回值是一个长度为2的数组（就是dp数组，dp[0]表示不选该节点的金额，dp[1]表示选择该节点的金额）；
第二，确定终止条件：当前节点为空时，无论选与不选，金额都是0，因此返回{0,0}，这其实是dp数组的初始化；
第三，确定遍历顺序：后序遍历，左右中；
第四，确定单层递归的逻辑，实质是对【中】的处理：如果不选该节点，那么左右孩子都可以考虑选（也可能不选，由max决定），需要取其最大值；如果选择该节点，那么左右孩子都不能选（这不存在考虑，只能是不选）。
最后遍历整棵树，返回的是头节点的两种状态下的金额，取其max即可。

    vector<int> robTree(TreeNode* cur)
    {//树的dp，返回值即dp数组，dp[0]:不选择cur的最大金额，dp[1]:选择cur的最大金额
        //1.终止条件，即dp数组的初始化
        if(cur==nullptr)
            return {0,0};   
        //2.遍历顺序：后序遍历--左右中
        vector<int> left=robTree(cur->left);
        vector<int> right=robTree(cur->right);
        //3.单层逻辑处理，即中的处理
        int val1=max(left[0],left[1])+max(right[0],right[1]);   //不选择cur，左右孩子可以选
        int val2=cur->val+left[0]+right[0]; //选择cur，要求左右孩子均不能选
        return {val1,val2}; //最终返回的是头节点的dp数组
    }
    int rob(TreeNode* root) {
        vector<int> res=robTree(root);
        return max(res[0],res[1]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17