我的笔记

Appearance

🍕 树型 DP ​

如果一个题目，能够通过向左子树有一个信息，向右子树要一个信息，然后就能得出我们想要的信息。那么这个题目就可以使用树型 DP 来解决

案例1 求一棵树的最大距离 ​

【思考】：

  • 最大距离有两种
    • 这个距离需要通过头节点
    • 这个距离不需要通过头节点
  • 当距离不需要通过头节点时，这个最大距离就是左右两个子树的最大距离
  • 当距离通过头节点时，这个距离就是左子树的最大高度＋右子树的最大高度＋１。
  • 所以，我们只需要向两边的子树要两个信息:
    • 最大距离是多少
    • 最大高度是多少
  • 然后我们从　“左子树的最大距离”　、　“右子树的最大距离”　和　“左右子树的最大高度＋１”　中找出最大值，这个最大值就是当前头节点的最大距离。

这种套路 —— 根据　“头节点”　是否参与这个过程，来列举出所有的可能性。在树型ＤＰ中是非常常见的。

java
Info process(Node x) {
    if (x == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int p1 = leftInfo.maxDistance;
    int p2 = rightInfo.maxDistance;
    int p3 = leftInfo.height + 1 + rightInfo.height;
    int maxDistance = max(p1, p2, p3);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    return new Info(maxDistance, height)
}

案例2 最大快乐值 ​

派对的最大快乐值。 每一个员工都有两个属性：

  • 本身的快乐值属性
  • 他的直接下属 现在对一个公司的所有员工发请帖，但是要遵循如下规则：
  • 如果邀请了一个员工，则不能再邀请该员工的直接下级（间接下级可以邀请）
  • 在满足条件1的情况下，邀请的员工一定回来 问如何邀请，能获得最大快乐值——所有来的员工的快乐值累加

【分析】：

  • 还是前面的套路，这就是一棵树，虽然是多叉树，但原理是一样的。分析头节点参不参与，可以得出两种可能性
    • 如果头节点参与，则它的最大快乐值是该节点的快乐值，加上所有子节点不参与的最大快乐值
    • 如果头节点不参与，则每个子节点都可以参与，也可以不参与，所以要比较子节点（直接下级）参与时的最大的快乐值和不参与时的最大快乐值。
  • 最后，获取根节点的最大快乐值，比较根节点参与的最大快乐值和不参与的最大快乐值，然后返回
  • 最大快乐值，其实就是最大收益，换汤不换药。
  • 所以，每个头节点需要向每个子节点要以下信息：
    • 参与时的最大收益（最大快乐值）
    • 不参与时的最大收益（最大快乐值）
  • 然后头节点根据子节点的信息，整合出自己要返回的信息
    • 头节点参与，则最大收益是所有子节点不参与时的最大快乐值累加
    • 头节点不参与，则最大收益是 max(子节点参与时的快乐值, 子节点不参与时的最大快乐值)。
java

class Employee {
    int happy; // 该员工的快乐值（ 收益）
    List<Employee> nexts; // 该员工的直接下级（多个子节点）
}
class Info {
    int comeMaxHappy; // 参加时，能获得的最大快乐值（最大收益）
    int noComeMaxHappy; // 不参加时，能获得的最大快乐值（最大收益）
}
int maxHappy(Employee boss) {
    Info headInfo = process(boss);
    return Math.max(headInfo.comeMaxHappy, headInfo.noComeMaxHappy);
}
Info process(Employee x) {
    if (x.nexts.isEmpty()) {
        // x 是基层员工（叶子节点）时，如果参加，则最大快乐值（最大收益）就是自己的快乐值，不参加，则最大快乐值是０。
        return new Info(x.happy, 0);
    }
    int come = x.happy; // x 参加，以 x 为头节点能获取的最大值
    int no = 0; // x 不参加，以 x 为头节点能获得的最大值
    for (Employee next: x.nexts) {
        Info nextInfo = process(next);
        come += nextInfo.noComeMaxHappy; // x 参加，则直接下级一定不能参加
        no += Math.max(nextInfo.comeMaxHappy, nextInfo.noComeMaxHappy);　// x 不参加，则直接下级可以参加，也可以不参加。
    }
    return new Info(come, no);
}