198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
dp[i] 表示前 i 间房，最多可以偷窃的金额为 dp[i]；
取决于 前 i - 1 间房最多可以偷窃的金额为 dp[i - 1] 和 第 i 间房偷不偷；
- 如果偷第
i间房，那么第i - 1间房一定不偷；dp[i]取决于 前i - 2间房最多可以偷窃的金额为dp[i - 2]加上 第i间房的金额；
即：dp[i] = dp[i - 2] + nums[i]； - 如果不偷第
i间房，dp[i]取决于 前i - 1间房最多可以偷窃的金额为dp[i - 1]；此时第i - 1间房可能偷， 也可能不偷；
即：dp[i] = dp[i - 1]；
最后，前 i 间房，最多可以偷窃的金额为，dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);( i >= 2 )；
当 i = 0 时，只有一间房，dp[0] = nums[0] ；
当 i = 0 时，有两间房，偷其中较大的一间，dp[0] = max(nums[0], nums[1]) ；
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) { // 防止取 dp[1] 时溢出
return nums[0];
}
vector<int> dp = vector<int>(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
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
成环后， 第一个房子和最后一个房子相邻，两者只能选择其中一个偷窃；
问题就变成了：
- 不偷窃第一个房子
nums[1]，最大金额是max1；（最后一个房子可能被偷） - 偷窃第一个房子
nums[1]，一定不偷窃最后一个房子nums[nums.size()−1]，最大金额是max2；
最后偷窃最大金额为： max(max1, max2) 。
class Solution {
public:
int robRange(vector<int>& nums, int start, int end) {
if (end - start == 1) { // [start, end)
return nums[start];
}
vector<int> dp(nums.size(), 0);
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 - 1];
}
int rob(vector<int>& nums) {
if (nums.size() == 1) {
return nums[0];
}
return max(robRange(nums, 0, nums.size() - 1), robRange(nums, 1, nums.size()));
}
};
337.打家劫舍III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。
选根节点，左右儿子都不能选；
不选根节点，左右儿子可能选；其中左右儿子之间没有影响；
选当前根节点，最大偷盗金额 = 不选左儿子的最大金额 + 不选右儿子的最大金额 + 当前节点值；
不选当前根节点，最大偷盗金额 = max(选左儿子的最大金额, 不选左儿子的最大金额) + max(选右儿子的最大金额, 不选右儿子的最大金额)；
最后，答案为：max(选根节点, 不选根节点)；
采用后序遍历
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};
}
};