198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统， 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
思路
每个房间是否被偷，主要取决于前一个和前两个房屋是否被偷了。因此一旦发现某种当前状态与前面状态的依赖关系，就应想到这是动规的递推公式。
- dp数组及其下标含义：考虑 包括
i号房屋在内，能偷窃的最大金额为dp[i]（PS: 仅考虑，并非实际选择偷取) -
递推公式：根据一些例子理解这种前后状态关系：
- 如果考虑要偷第5间房，那么第4间就必定不再考虑，此时的状态是确定选择第5间并开始考虑第3间；
dp[i-2]+nums[i] - 如果考虑不偷第5间房，那么就可以开始考虑第4间；
dp[i-1]
因此递推公式为：
dp[i] = max(dp[i-2]+nums[i], dp[i-1]) - 如果考虑要偷第5间房，那么第4间就必定不再考虑，此时的状态是确定选择第5间并开始考虑第3间；
-
数组初始化：考虑前两个状态的递推公式，其基础都是dp[0]和dp[1]。在该问题中，
- 考虑仅包含第0间房的能偷窃最大金额必定为dp[0]=nums[0]；
- 考虑包含第0和第1间房的能偷窃最大金额则是max(nums[1], nums[2])
- 遍历顺序：当前状态取决于前两个状态，自然是从前向后遍历
- 举例推导：一个例子如下图所示：
代码实现
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
vector<int> dp(nums.size());
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];
}
};
213. 打家劫舍 II
这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
思路
本题相较于上题多了一个首尾相连的机制，那么在考虑上一间和上两间的基础上，还要额外考虑是偷 首间 还是 尾间？其余部分均与 198. 打家劫舍I 同理
代码实现
一种实现方法，是先将基本的打家劫舍封装成函数，再针对首尾相连的两种情况分别考虑
class Solution {
public:
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);
return max(result1, result2);
}
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];
}
};
在进行递推循环时，切记是从dp[2]开始的，因为0,1都已经初始化了
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
思路
本题是二叉树递归遍历形式的打家劫舍，其实就是把 DP 融合到树的递归过程中。
代码实现
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};
}
};
后记
- 打家劫舍问题与基本的动态规划问题区别不大，核心都是将最终状态分解为过去两个相关的状态；
- 其难点在于房舍的结构，使其可以很自然的与循环数组、二叉树、图等结构相关联，从而产生交叉题目。
