198. 打家劫舍
1. LeetCode链接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2. 题目描述
3. 解法
可以看作一个01背包问题。背包容量为所有房子中存储的金钱总数。
1. dp数组含义：dp[i][j]表示前i个房子在背包容量为j的情况下可以偷盗的最大金额。
2. 递推公式：dp[i][j]等于不加当前房子金额时的和加当前房子金额时中的最大值。即dp[i][j] = dp[i - 1][j] + bdp[i - 2][j - nums[i]] + nums[i]（由于不能在相邻房子中偷盗，所以偷盗当前房子时，应该加到上上一行的数上）
3. dp数组初始化：仅用2 * (sum + 1)容量的数组，用nums[0]，nums[1]初始化数组。
4. 遍历顺序：物品从第三个开始到最后，注意！！物品遍历时，dp数组的行数跟着遍历，dp数组的列数从后往前遍历。
5. 举例。
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
int sum = 0;
for (int i : nums) sum += i;
vector<vector<int>> dp(2, vector<int>(sum + 1, 0));
for (int i = nums[0]; i < sum + 1; i++) dp[0][i] = nums[0];
for (int i = 0; i < sum + 1; i++) dp[1][i] = (i >= nums[1] ? max(nums[1], dp[0][i]) : dp[0][i]);
for (int j = 0, i = 2; i < nums.size(); j = (j + 1) % 2, i++) {
for (int k = sum; k >= 0; k--) {
dp[j][k] = (k >= nums[i] ? max(dp[j][k - nums[i]] + nums[i], dp[(j + 1) % 2][k]) : dp[(j + 1) % 2][k]);
}
}
return nums.size() % 2 == 0 ? dp[1][sum] : dp[0][sum];
}
};更简单的方法：
1. dp数组含义：dp[i]表示包括前i个物品的情况下可盗取的最大金额。
2. 递推公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
3. dp初始化：只初始化dp[0]和dp[1]。
4. 遍历顺序：依次多考虑一件物品。
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size(), 0);
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. LeetCode链接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2. 题目描述
3. 解法
头尾两个房间不能同时盗取，所以考虑三种基本打家劫舍情况，1. 不包含头尾的基本打家劫舍；2. 包含头但不包含尾的基本打家劫舍；3. 不包含尾仅包含头的打家劫舍。而第一种情况包含在2、3中。
所以只需要计算2、3两种情况。然后取两种情况中的最大值。
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
vector<int> dp(nums.size(), 0);
vector<int> dp1(nums.size(), 0);
dp1[1] = nums[1];
dp1[2] = max(nums[1], nums[2]);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 3; i < nums.size(); i++) {
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
for (int i = 2; i < nums.size() - 1; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return max(dp[nums.size() - 2], dp1[nums.size() - 1]);
}
};我首先想的是利用一个bool数组记录当前最大是否用到了头元素。在这种情况下，当最终的最大值是同时考虑头尾的情况，如果是简单的减去头尾之中的最小值，所得结果仍然不是最终答案。因为同时考虑头元素和尾元素的最终答案，在减去头尾中的最小元素后，与nums中去掉头元素而成的基本打家劫舍问题的最终答案，是完完全全的两个概念。
337. 打家劫舍III
1. LeetCode链接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2. 解法
递归后序遍历二叉树，考虑每个节点偷与不偷的情况。
1. 递归参数和输出：参数包含树的节点。输出为当前节点偷与不偷两种情况下各自的最大值所组成的数组，即dp数组。
2. 终止条件：树节点为空，返回0，0；
3. 单层递归逻辑：计算左右孩子的dp数组，根据左右孩子的dp数组，计算当前节点的dp数组。1）不偷当前节点时，数值为左dp最大值 + 右dp最大值；2）偷当前节点时，数值为当前节点值 + 左不偷 + 右不偷。
class Solution {
public:
vector<int> robTree(TreeNode* root) {
if (root == nullptr) return {0, 0};
vector<int> bp(2, 0);
vector<int> left = robTree(root->left);
vector<int> right = robTree(root->right);
bp[0] = left[1] + right[1] + root->val;
bp[1] = max(left[0], left[1]) + max(right[0], right[1]);
return bp;
}
int rob(TreeNode* root) {
vector<int> bp = robTree(root);
return max(bp[0], bp[1]);
}
};
