代码随想录第四十八天 | 198.打家劫舍， 213.打家劫舍II，337.打家劫舍III

198.打家劫舍

看完想法：这里的偷/不偷，和背包问题中的放/不放感觉是一个道理，所以在dp递推公式中仍旧使用max(dp[i-2] + nums[i], dp[i-1])

int rob(vector<int>& nums) {vector<int> dp(nums.size()+1,0);if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);//0和1的情况要单独用if列出，所以这里起始点是i=2for(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

看完想法：考虑首尾元素不能同时选的情况，我们分只选首元素和尾元素的情况，这两种情况都算一个dp，然后取最大值就可以。为什么dp不为nums.size() + 1呢？因为dp定义是考虑i之内的房屋，不必要使用

int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int dp1 = robRange(nums, 0, nums.size() - 2);//只考虑首部元素的情况int dp2 = robRange(nums, 1, nums.size() - 1);//只考虑首部元素的情况int result = max(dp1, dp2);return result;}//不要囿于实际dp数组的思路，这里是写函数，参数用形参int robRange(vector<int>& nums, int start, int end){vector<int> dp(nums.size());if(start == end) return nums[start];//记得初始化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-1], dp[i-2] + nums[i]);}return dp[end];}

337.打家劫舍III

看完想法：对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）不记得快去复习一下知识点。解题从递归树的递归三部曲来解题。因为题目中考虑了偷或者不偷两种结果，那最终程序输出取什么呢？当然是取最大的啦，和递归顺序中取偷/不偷的逻辑是一样的。最近面试被问到了时间复杂度，做题的时候还是要分析一下。

class Solution {
public:vector<int> robTree(TreeNode* cur){//确定终止条件if(cur == nullptr) return vector<int>{0,0};//递归顺序vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur，那么就不能偷左右节点,所以是left[0] + right[0]int val1 = cur->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右节点，则取left/right中偷不偷较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}