打家劫舍系列总共有三道，难度设计非常合理，层层递进。第一道是比较标准的动态规划问题，而第二道融入了环形数组的条件，第三道更绝，让盗贼在二叉树上打劫，这就是传说中的高智商犯罪吧。。。

    • 第一题

    打家劫舍问题 - 图1
    第一种类型的动态规划，还是一维数组的。

    • 第二题

      你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

      给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

    示例 1： 输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

    示例 2： 输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。

    示例 3： 输入：nums = [0] 输出：0

    因为是环形的房屋，所以dp[0]也受最后一间房的影响。本题的策略是按照取与不取第一间房来讨论，取这两种情况的最佳得分即可。

    1.     int rob(vector<int>& nums) {
    2.         if(nums.empty()) return 0;
    3.         if(nums.size()==1) return nums[0];
    4.         int N=nums.size();
    5.         vector<int> dp(nums.size());
    6.         //取arr[0]
    7.         dp[0]=nums[0];
    8.         dp[1]=dp[0];
    9.         for(int i=2;i<nums.size()-1;++i){
    10.             dp[i]=max(dp[i-1],nums[i]+dp[i-2]);
    11.         }
    12.         int value1=dp[nums.size()-2];
    13.         //不取arr[0]
    14.         dp[0]=0;
    15.         dp[1]=nums[1];
    16.         for(int i=2;i<nums.size();++i){
    17.             dp[i]=max(dp[i-1],nums[i]+dp[i-2]);
    18.         }
    19.         return max(value1,dp[N-1]);
    20.     }
    • 第三题

      在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

      计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

    示例 1: 输入: [3,2,3,null,3,null,1]

     3
/ \

    2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

    示例 2: 输入: [3,4,5,1,3,null,1]

     3
/ \

    4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

    二叉树的后序处理方式即可。

         //备忘录
    unordered_map<TreeNode*,int> memo;
    //后序处理
    int rob(TreeNode* root) {
        if(root==nullptr) return 0;
        if(memo.find(root)!=memo.end()) return memo[root];
        int child=0;
        int grandson=0;
        if(root->left){
            child+=rob(root->left);
            grandson+=(rob(root->left->right)+rob(root->left->left));
        }
        if(root->right){
            child+=rob(root->right);
            grandson+=(rob(root->right->left)+rob(root->right->right));
        }
        int choose=max(root->val+grandson,child);
        memo[root]=choose;
        return choose;
    }