首先状态表示,对于每个节点来说,都有选择或者不选择两种状态,父亲节点的状态由子节点状态推算而来,比如我们选择了子节点,那么父亲节点肯定不能选择,如果我们不选择父亲节点,那么子节点可以选择也可以不选择。状态表示完成了,接下来就是状态转移。
我们假设dp[root][0]是未选择该节点产生的价值,dp[root][1]是选择了该节点产生的价值,那么我们就可以得到状态转移方程:
dp[root][0]+=max(dp[left][1].dp[left][0]),dp[root][0]+=max(dp[right][1].dp[right][0]);
假设根节点不选择,我们既可以选择子节点,也可以不选择子节点
dp[root][1]+=dp[left][0],dp[root][1]+=dp[right][0];
假设选择了根节点,两个字节点都不能选择
点击查看代码
class Solution {
public:
pair<int,int> dfs(TreeNode* root)//这里dfs返回一个pair数据类型
{
pair<int,int>res={0,root->val};//first代表未选择该节点是产生的价值,second代表选择了该节点是产生的价值
//故first初始化为0,second初始化为自己本身的价值
if(root->left!=nullptr){//如果左子节点存在
auto x=dfs(root->left);//此时要调用dfs,从左子节点继续往下找,计算完左子节点的价。
//也就是说我们会一直找这个节点的左子节点。
//这个节点的左子节点的左子节点。直到某个节点不存在左子节点,再一个个往上推导
res.first+=max(x.first,x.second);//假设自己本身不选择,那么左子节点可以选择也可以不选择,我们选择两者的最大值加上
res.second+=x.first;//如果自己本身选择了,那么左子节点肯定不能选择
}
if(root->right!=nullptr){//与左子节点同理
auto x=dfs(root->right);
res.first+=max(x.first,x.second);
res.second+=x.first;
}
return res;
}
int rob(TreeNode* root) {
auto x= dfs(root);
return max(x.first,x.second);//选取 选择根节点和不选择根节点之间的最大值
}
};