本博客是记录作者做动态规划算法的和打家劫舍相关的中等难度题的笔记。

LeetCode题目 相关题目类型 题目类型分析 题目思路 相关链接
198 打家劫舍（中等难度） 一排有不同金额的房屋，相邻房屋不能偷，求能偷的最大金额 dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]，决定dp[i]的因素就是第i房间偷还是不偷。 198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com)
213 打家劫舍II（中等难度） 一圈有不同金额的房屋，相邻房屋不能偷，求能偷的最大金额 当有多余两间房的时候：考虑首位相连问题。取了第一间房，就不能要最后一间房：[0, n-2] ； 取了最后一间房，就不能要第一间房：[1, n-1]；对这两段用普通的打家劫舍算法，再取这两段的最大值返回。 213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com)
337 打家劫舍III（中等难度） 二叉树形状的动态规划，父子节点不能同时偷 偷当前节点,左右孩子就都不能偷，偷当前节点，左右孩子可以偷也可以不偷；递归函数返回一个长度为2的数组，0：不偷，1：偷 337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

198 打家劫舍

这道题目非常好理解，其求最大金额，在盗窃时存在多种方案，所以才会有最大金额。

以[1,2,3,1]为例，为了不触发警报，小偷可以选择1，3和2，1，比较其谁更大就选择谁

假设dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。，显然

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

代码如下：

int rob(vector<int>& nums) {
        /*输入一个数组，输出一个整数*/
        if(nums.size()==1){
            return nums[0];
        }
        vector<int> dp(nums.size());//dp[i]表示加上第i个房屋后一共可以盗窃的最大金额
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        // 推导dp数组
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        
        return dp[nums.size()-1];
    }

213 打家劫舍II

这道题目的关键是明白 第n个台阶只能从第n-1或者n-2个上来，所以到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法。

int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());//动归数组
        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];
    }
    int rob(vector<int>& nums){
        /*输入一个整数数组，输出一个数组
        * 思路如下：
     *      1. 当只有一间房的时候，直接返回这个返回金额。
     *      2. 当有两间房的时候，返回这两个房间的最大值。
     *      3. 当有多余两间房的时候：考虑首位相连问题。
     *          取了第一间房，就不能要最后一间房：[0, n-2]
     *          取了最后一间房，就不能要第一间房：[1, n-1]
     *      对这两段用普通的打家劫舍算法，再取这两段的最大值返回。
        */
        if(nums.size()==1){
            return nums[0];
        }
        int result1 = robRange(nums, 0, nums.size() - 2); // 取了第一间房，就不能要最后一间房：[0, n-2]
        int result2 = robRange(nums, 1, nums.size() - 1); // 取了最后一间房，就不能要第一间房：[1, n-1]
        return max(result1, result2);
    }

337 打家劫舍III

整理后的代码如下：

// 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷当前节点,左右孩子就都不能偷
        int val1 = cur->val + left[0] + right[0];
        // 不偷当前节点，左右孩子可以偷也可以不偷
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }