前言

今年，五一假期出不去玩，要不也一起来学会习。
觉得有帮助的，要不三连一下~

一、打家劫舍

这类题型，主要分为偷与不偷两种情况。

dp[i]: 包括下标i以内的房屋的最多可偷窃的金额

状态转移方程一般为:

dp[i] = max(dp[i-2] + nums[i], dp[i-1])

打家劫舍

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 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

1. 确定dp数组以及下标含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2. 确定递推公式

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

偷第i，要注意隔一个房子，只能考虑i-1

不偷第i，可以考虑i-1的房子

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3. 初始化

根据含义进行初始化,dp[0] = nums[0],

dp[1] = nums[1];

4. 遍历顺序
5. 距离推导dp数组

class Solution {public:    int rob(vector<int>& nums) { // 这道题难点在于偷与不偷 int n = nums.size(); if(n<=1) return nums[0]; if(n<=2) return max(nums[0], nums[1]); // dp[i] 考虑i以内房间的时候的最大金额 vector<int> dp(n+1, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for(int i = 2; i < n; ++i){     // 偷 要隔开， 不偷可以考虑i-1的情况     dp[i] = max(dp[i-2] + nums[i], dp[i-1]); } return dp[n-1];    }};

打家劫舍II

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 = [0] 输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

分析：成环了

则在上一题的基础上分成两种情况。

1. 考虑了首元素，不考虑尾元素
2. 考虑了尾元素，不考虑首元素

class Solution {public:    int robRange(vector<int>& nums, int start, int end) { int n = end - start + 1;// 注意一下遍历的区间 if(n<=1) return nums[start]; if(n<=2) return max(nums[start], nums[start + 1]); // dp[i] 考虑i以内房间的时候的最大金额 vector<int> dp(nums.size(), 0); dp[start] = nums[start]; dp[start+1] = max(nums[start], nums[start+1]); // [start+2,end] for(int i = start + 2; i < end; ++i){     // 偷 要隔开， 不偷可以考虑i-1的情况     dp[i] = max(dp[i-2] + nums[i], dp[i-1]); } return dp[end-1];// 注意范围的问题    }    int rob(vector<int>& nums) { int n = nums.size(); if(n<=1) return nums[0]; if(n<=2) return max(nums[0], nums[1]); int leftRange = robRange(nums, 0, n-1); int rightRange = robRange(nums, 1, n); return max(leftRange, rightRange);    }};

打家劫舍 III

337.打家劫舍 III

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

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

思路：

由于偷与不偷要考虑左右节点

因此只能采取后序遍历

这题其实更像是树上做dp

1. dp数组

dp[i] 下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

2. 单层遍历的逻辑

• 如果偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];
• 如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

class Solution {public:    int rob(TreeNode* root) { vector<int> result = robTree(root); return max(result[0], result[1]);    }    // 长度为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); // 偷cur int val1 = cur->val + left[0] + right[0]; // 不偷cur int val2 = max(left[0], left[1]) + max(right[0], right[1]); return {val2, val1};    }};

小结：

dp[i]: 包括下标i以内的房屋的最多可偷窃的金额

状态转移方程一般为:

dp[i] = max(dp[i-2] + nums[i], dp[i-1])
看到着了都，要不点个赞

参考资料

代码随想录
LeetCode