第三十九天打卡，今天解决打家劫舍系列问题，树形dp比较难。
198.打家劫舍
题目链接
解题过程
- dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
- 要么不偷这一间，那就是前面那间赚的多；要么偷这一间，加上前前一间最多偷的金额。
动态规划
class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if (len == 0) return 0;if (len == 1) return nums[0];if (len == 2) return max(nums[0], nums[1]);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 - 1], dp[i - 2] + nums[i]);}return dp.back();}
};
213.打家劫舍Ⅱ
题目链接
解题过程
- 与打家劫舍Ⅰ的区别就是，这里第一个元素和最后一个元素不能同时选择，所以分两种情况就可以做
动态规划
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];if (nums.size() == 2) return max(nums[0], nums[1]);int rob1 = getRob(nums, 0, nums.size() - 2);int rob2 = getRob(nums, 1, nums.size() - 1);return max(rob1, rob2);}int getRob(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];}
};
337.打家劫舍Ⅲ
题目链接
解题过程
- 没想到这题怎么做，用树形dp，每个节点记录偷或者不偷该点能偷得的总共最大钱数。用后序遍历，因为要用到子节点的结果
树形dp
class Solution {
private:vector<int> backtracking(TreeNode* node) {if (node == nullptr) return { 0,0 }; vector<int> left = backtracking(node->left);vector<int> right = backtracking(node->right);int val1 = max(left[0], left[1]) + max(right[0], right[1]); // 不偷该节点，可以偷或不偷左右节点int val2 = left[0] + right[0] + node->val; // 偷该节点，则不能偷子节点return { val1,val2 };}public:int rob(TreeNode* root) {vector<int>result = backtracking(root);return max(result[0], result[1]);}
};
