Leetcode：198. 打家劫舍、213. 打家劫舍 II、337. 打家劫舍 III（C++）

目录

198. 打家劫舍

问题描述：

实现代码与解析：

动态规划（版本一）：

原理思路：

动态规划（版本二）：

原理思路：

213. 打家劫舍 II

问题描述： 

实现代码与解析：

动态规划：

原理思路：

337. 打家劫舍 III

问题描述：

实现代码与解析：

动态规划（树形dp）：

 原理思路：

---

198. 打家劫舍

问题描述：

        你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

实现代码与解析：

动态规划（版本一）：

class Solution {
public:int rob(vector<int>& nums){//先把前两个单独弄出来返回if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];//dp含义, 按顺序偷第 i 个屋子时获得的最大金额vector<int> dp(nums.size(), 0);//dp数组dp[0] = nums[0]; // 初始化dp[1] = nums[1];//遍历for (int i = 2; i < nums.size(); i++){//小于 3 的时候只能跳一个，所以单独计算一下喽if (i < 3) dp[i] = dp[i - 2] + nums[i];else{//跳一个或则跳两个，不能再多跳了，不然肯定会少偷，这两之间取最大喽dp[i] = max(dp[i - 2] + nums[i], dp[i - 3] + nums[i]);// 偷 i - 2的屋子时获得的最大金额，加上此屋子的金额,和偷 i - 3 的屋子时获得的最大金额加上此屋子金额取最大}}int result = max(dp[nums.size() - 1], dp[nums.size() - 2]);//倒数第一个和倒数第二个比较，因为最后偷的肯定是这两个房间之一return result;}
};

原理思路：

        这里dp数组的含义是偷第 i 个屋子后能获得的最大价值，有点像爬梯子，大家看注释就能懂，但是其实是写的麻烦了，所以大家看版本二就可以了，要简洁很多。

动态规划（版本二）：

class Solution {
public:int rob(vector<int>& nums){//先把前两个单独弄出来返回if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];//dp含义, 按顺序选择0~i的屋子是否偷取时获得的最大金额vector<int> dp(nums.size(), 0);//dp数组//初始化dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for(int i = 2; i < nums.size(); i++){dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};

原理思路：

        这里dp数组的含义是在1 ~ i 之间选择能获取的最大金额。

        所以房间有两种状态，一种是偷，那么我们就找出 i - 1 能获取的最大金额，然后加上 nums[ i ]就为此时的如果偷的最大金额，一种是不偷，那么我们肯定是偷了 i - 1 编号的房间，此时dp[ i - 1] 为不偷的最大价值，两个之间进行比较，就求出了对于 i 房间偷或不偷选择出的最大金额，也就是dp[ i ]了。   

213. 打家劫舍 II

问题描述： 

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

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

示例 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 = [1,2,3]
输出：3

实现代码与解析：

动态规划：

class Solution {
public:int robRange(vector<int>& nums,int start,int end){if(start == end) 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 - 1], dp[i - 2] + nums[i]);}return dp[end];}int rob(vector<int>& nums) {if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 不选取最后有一个房间的最大价值int result2 = robRange(nums, 1, nums.size() - 1);   // 不选取第一个房间的最大价值int result = max(result1, result2);return result;}
};

原理思路：

        相比于打家劫舍Ⅰ了一个限制条件，就是房屋练成环了，所以无非就两种情况，一种是首尾两个房间都不偷，一种是首尾两个房间偷其中一个，根据Ⅰ的思路我们只要算出，不选取最后一个房间的最大金额和不选取第一个房间的最大金额，两个之中取最大就可以了，所以就比Ⅰ多了个选最大的操作而已，其他相似照着写就行。

337. 打家劫舍 III

问题描述：

        小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

 

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9s

实现代码与解析：

动态规划（树形dp）：

class Solution {
public://dp数组含义，0为不偷cur房间，1为偷cur房间vector<int> robTree(TreeNode* cur){//没有房间，返回0if(cur == NULL) return vector<int>{0,0};//左右子树偷或不偷的最大金额vector<int> leftDp = robTree(cur -> left);vector<int> rightDp = robTree(cur -> right);int value1 = leftDp[0] + rightDp[0] + cur -> val;// 此房间偷，那么其子树肯定不偷int value2 = max(leftDp[0], leftDp[1]) + max(rightDp[0], rightDp[1]);//不偷cur，此时判断其左右子树偷或不偷的最大值，不要认为一定偷子树就为最大值，一定要比较一下return {value2, value1};}int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}
};

 原理思路：

        这里房间的连接变为二叉树的连接方式了，题目描述还是相连接的不能一起偷。

        这里我们的dp数组的含义就发生改变了，dp为一个长度为2的数组，dp[ 0 ]表示不偷当前房间的最大金额，dp[ 1 ]表示偷当前房间的最大金额，并且作为返回值。

        首先偷当前房间的递推公式好写，偷此房间，那么其孩子结点一定不偷：

dp[ 1 ] = leftDp[0] + rightDp[0] + cur -> val;

        而不偷当前房间的话，我们就要比较孩子结点偷或不偷的最大金额了，取最大，注意不要认为偷孩子结点就是最大金额，这是一个误区，一定要比较一下，万一孩子结点的孩子结点和大于孩子结点呢？此时的递推公式为：

dp[ 0 ] = max(leftDp[0], leftDp[1]) + max(rightDp[0], rightDp[1]);

        还有就是这里肯定是后序遍历，我们要知道孩子结点的信息。