算法-多叉树-组织party最大快乐值

2022-5-7 diaba 算法 

package com.jiucaiyuan.net.algrithm.tree;

import java.util.List;

/**
 * <pre>
 * 树形dp套路
 * 树形dp套路使用前提：
 * 如果题目求解目标是S规则，则求解流程可以定成每一个节点为头节点的子树
 * 在S规则下的每个答案，并且最终答案一定在其中
 * 案例题
 * 【题目】派对的最大快乐值
 * 员工信息定义如下
 * class Employee{
 * public int happy; //这名员工带来的快乐值
 * List<Employee> subordinates; //这名员工有哪些直接下级
 * }
 * 公司每名员工都符合Employee类的描述，整个公司的人员结构可以看做是
 * 标准的、没有环的多叉树，树的头结点可以看做是公司唯一的老板，除了老板
 * 外，每个员工都有唯一的上级。叶子结点是没有直接下级的基层员工（subordinates
 * 列表为null），除了基层员工外，每个员工都有一个或多个直接下级。
 * 这个公司要办party，你可以决定哪些员工来，哪些员工不来，但是要遵循
 * 如下规则：
 * 1.如果某个员工来了，那么这个员工的直接下级都不能来；
 * 2.派对的整体快乐值是到场的所有员工快乐值的累加；
 * 3.你的目标是让派对的整体快乐值最大；
 * 给定一个多叉树的头结点boss，请返回派对的最大快乐值
 * 【思路】
 * 划分为几种情况：
 * 1.头结点参与，最大快乐值=直属员工不参与的情况下最大快乐值的累加和；
 * 2.头结点不参与，轮训所有直属员工，直属员工来的情况下最大快乐值的累加和+直属员工不来的情况下最大快乐累加值；
 * 从两种中累加，就是整party最大的快乐值
 * 子树返回的结果：头结点来时的最大快乐值，头结点不来时的最大快乐值
 * </pre>
 *
 * @Author jiucaiyuan  2022/5/6 23:06
 * @mail services@jiucaiyuan.net
 */

public class MaxHappyValue {
    public static class Employee {
        public int happy;
        public List<Employee> subordinates;
    }

    public static class Info {
        public int yesMaxHappy;  //来的时候最大快乐值
        public int noMaxHappy;   //不来时最大快乐值

        public Info(int yes, int no) {
            this.yesMaxHappy = yes;
            this.noMaxHappy = no;
        }
    }

    /**
     * 取得以boss为老板的公司组织party获得的最大快乐值
     *
     * @param boss 整个公司唯一的老板
     * @return 最大快乐值
     */
    public static int maxHappy(Employee boss) {
        Info info = process(boss);
        return Math.max(info.yesMaxHappy, info.noMaxHappy);
    }

    /**
     * @param employee 当前员工来与不来获得的最大快乐值
     * @return
     */
    private static Info process(Employee employee) {
        if (employee == null) {
            return new Info(employee.happy, 0);
        }
        //当前员工来，再统计直属下级不来时最大快乐值累加
        int yes = employee.happy;
        //当前员工不来，再统计直属下级来与不来时最大快乐值累加
        int no = 0;
        for (Employee e : employee.subordinates) {
            Info eInfo = process(e);
            //当前员工来，直接下属不来时的快乐值
            yes += eInfo.noMaxHappy;
            //当前员工不来，下属可以来也可以不来，得到最大快乐值
            no += Math.max(eInfo.yesMaxHappy, eInfo.noMaxHappy);
        }
        return new Info(yes, no);
    }
}

« 算法-二叉树遍历-morris遍历 | 算法-二叉树-最大距离»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022