摘要：前面的都是简单的线性动规，本篇开始树形动规问题的入门.
1.正文：树是我最喜欢的数据结构（没有之一），它既不是像线性表那样过于单调的线性关系，又没有像图那样有着复杂的网状关系，规律的非线性关系常常是我们现实生活中诸多问题的基本模型，比如家族关系、企业架构等。当它与动态规划相结合时，似乎很高大上，但一言概之只是用一个树状的数据结构封装问题元素的动规问题而已，仍然是按动规的基本步骤走：
（1）题意分析；
（2）基于分析数学建模；
（3）判定是否可以符合使用动规的两大前置条件（最优子结构和无后效性），是则下一步，否则终止（非动规可以解决的问题，另寻他法）；
（4）动规基本三步曲：
1）结合题意根据模型选择计算出比较合适的状态转移方程，归约初始的状态值，推导出终止（最终收敛）条件；
2）迭代验证；
3）选择合适的迭代次序实现状态转移方程的迭代和收敛；
（5）编程实现。
万变不离其宗。不多赘述，看看今日有趣的例题。
2.题目：
经典例题（某度就有）
没有上司的晚会等
【问题描述】
有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。
3.输入输出示例：
输入：
第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x（-128<=x<=127）。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。
输出：
5
4.例程：
package algorithm;
import java.util.*;
/**
* @Project: texat
* @Author: h
* @Package: algorithm
* @Version: V1.0
* @Title:
* @Tag:
* @Description:
* @Date: 2020/6/9 23:40
*/
public class TreeDynamicSolution {
private static class TreeNode {
//父节点
TreeNode p = null;
//子节点
List<TreeNode> c = new ArrayList<>();
//父节点不来的最大气氛总值
int offVal = 0;
//父节点来的最大气氛总值
int onVal;
public TreeNode(int onVal) {
this.onVal = onVal;
}
}
public static void mainByTreeNode(String[] strings) {
//建树
HashMap<Integer, TreeNode> no2TreeNode = new HashMap<>();
HashSet<Integer> parentSet = new HashSet<>();
Scanner scanner = new Scanner(System.in);
int len = scanner.nextInt();
for (int i = 0; i < len; i++) {
int val = scanner.nextInt();
no2TreeNode.put(i + 1, new TreeNode(val));
parentSet.add(i + 1);
}
int targetVal = 0, parentVal = 0;
while (scanner.hasNextInt() && (targetVal = scanner.nextInt()) != 0) {
parentVal = scanner.nextInt();
no2TreeNode.get(targetVal).p = no2TreeNode.get(parentVal);
no2TreeNode.get(parentVal).c.add(no2TreeNode.get(targetVal));
parentSet.remove(targetVal);
}
//计算气氛值
Integer root = parentSet.iterator().next();
TreeNode treeNode = no2TreeNode.get(root);
sumMaxHappy(treeNode);
//输出
System.out.println(Math.max(treeNode.offVal, treeNode.onVal));
}
/**
* 链式存储：树节点递归
* @param root
* @return
*/
private static void sumMaxHappy(TreeNode root) {
if (null == root) {
return;
}
root.c.forEach(c -> {
sumMaxHappy(c);
root.offVal += Math.max(c.offVal, c.onVal);
root.onVal += c.offVal;
});
}
private static int[][] f;
private static boolean[][] link;
private static int[] happyVal;
public static void mainByArray(String[] strings) {
//申请数组空间
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
link = new boolean[count][count];
happyVal = new int[count];
f = new int[count][2];
boolean[] isNotRoot = new boolean[count];
//录入
for (int i = 0; i < count; i++) {
int val = scanner.nextInt();
happyVal[i] = val;
}
int target, parent;
while (scanner.hasNextInt() && (target = scanner.nextInt()) != 0) {
parent = scanner.nextInt();
isNotRoot[target - 1] = true;
link[parent - 1][target - 1] = true;
}
int root = -1;
for (int i = 0; i < count; i++) {
if (!isNotRoot[i]) {
root = i;
break;
}
}
//计算气氛值