代码随想录训练营第39天|树形dp

198. 打家劫舍

class Solution {
public:int rob(vector<int>& nums) {nums.insert(nums.begin(),0);int n=nums.size();vector<int> dp(n,INT_MIN);dp[0]=0;dp[1]=nums[1];for(int i=2; i<n; i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[n-1];}
};

dp[i]：截止下标i(包含i）的房子，所能打劫的最大金额

转移方程：考虑nums[i]是否被打劫，只有两种可能：

抢，那么为了不触发警报，nums[i-1]一定不能被打劫，只能从i-2转移而来
不抢，则nums[i-1]可以被抢，最大金额就等于dp[i-1]

引入空房间作为虚拟头，初始化更简单，且不影响最终结果。

213. 打家劫舍 II

class Solution {
public:int rob_range(vector<int>& nums, int left, int right) {if(left==right)return nums[left];int n=nums.size();vector<int> dp(nums.size(),INT_MIN);dp[left]=nums[left];dp[left+1]=max(nums[left+1],nums[left]);for(int i=left+2; i<=right; i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[right];}int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];int amount1=rob_range(nums,0,nums.size()-2);int amount2=rob_range(nums,1,nums.size()-1);return max(amount1,amount2);}
};

上题的变种，题目可以拆分为两种情况：抢第一间或不抢第一间。分别处理取最大即可

337. 打家劫舍 III

class Solution {
public:pair<int,int> rob_tree(TreeNode* root){if(root==nullptr)return {0,0};auto [left_0, left_1]=rob_tree(root->left);auto [right_0, right_1]=rob_tree(root->right);int root_1=root->val+left_0+right_0;int root_0=max(left_0,left_1)+max(right_0,right_1);return {root_0,root_1};}int rob(TreeNode* root) {auto [root_0, root_1]=rob_tree(root);return max(root_0,root_1);}
};

状态转移：定义rob_tree返回的是pair：{不抢根的最大值，抢根的最大值}

采用后续遍历，利用子树的结果构建当前结果，也是分治的思想，即把当前问题拆解为规模更小的子问题，直到空树，一定为{0，0}。

对于当前层的计算逻辑，分两种情况：