树型动态规划就是在“树”的数据结构上的动态规划，树型动态规划是建立在树上的，所以有二个方向： 1．根—>叶：这种题目基本上碰不到 2．叶－>根：根的子节点传递有用的信息给根，完后根得出最优解的过程。这种的题目是树型动态规划的最常见类型。 首先定义
无根树：题目中可以以任意节点为根建树，经过动态规划后即可直接得到最优值。
有根树：必须以某一个节点为根建树才能通过动态规划后得到最优值。
基本上有这样一个步骤：
一、有根树：
1.建树（一般以递归方式实现，有时数据过大以BFS方式实现）
2.在建树中找到叶子的时候特别赋值。
3.回溯时通过方程确定出每个节点的最优值并记录。
4.遍历完整棵树后一般以根节点值作为最终值。
- 补充:关于建树，有很多时候会将原来的多叉树改造为左孩子右兄弟的二叉树，以下两道例题用到了这种改造。
- 例题1:Tyvj P1051 选课
//简单的改造代码:
for i:=1 to n do
if ft[root[i]]=false then//这个节点目前还没有孩子
begin
a[root[i]].left:=i;//把这玩意儿放到当前节点的左边
ft[root[i]]:=true;//标记-有孩子了
num[root[i]]:=i;//该节点当前最后一个孩子
end
else//有孩子了
begin
a[num[root[i]]].right:=i;//把这玩意儿给他当前最后一个孩子的右边
num[root[i]]:=i;
end;//By 澹台彦澍
二、无根树：
1.随机定根，重复有根树过程
2.要枚举节点作为根的情况重复有根树过程。