树形DP：打家劫舍3

系统管理员 2023-10-06 13:58 16阅读 0赞

## 树形DP：打家劫舍3 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路： ####

每个节点有选和不选两种状态，若选，则其孩子节点不可选，若该节点不选，则孩子节点可选也可不选

设DP\[u\]\[0\]表示不选当前结点u的情况下以u为根的子树所能得到得最大价值  
DP\[u\]\[1\]表示选当前结点u的情况下以u为根的子树所能得到得最大价值  
设v为其孩子节点

![在这里插入图片描述][20200731081932418.png]  
![在这里插入图片描述][20200731082106854.png]  
使用pair保存选或不选两种情况的值，通过DFS求解

#### 代码： ####

class Solution {
        
    public:
        pair<int, int> dfs(TreeNode *root) {
        
            if (root == nullptr) {
        
                return {
         0, 0 };
            }
            auto left_pair = dfs(root->left);
            auto right_pair = dfs(root->right);
            return {
         root->val + left_pair.second + right_pair.second, 
                    max(left_pair.first, left_pair.second) + max(right_pair.first, right_pair.second) };
        }
        
        int rob(TreeNode* root) {
        
            auto p = dfs(root);
            return max(p.first, p.second);
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200731080155293.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200731080205404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20200731081932418.png]: https://img-blog.csdnimg.cn/20200731081932418.png
[20200731082106854.png]: https://img-blog.csdnimg.cn/20200731082106854.png