目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。

大多数动规都是在一维二维这种规则的背景下的，可以解决的问题比较局限，而树作为一种特殊的图，可以描述比较复杂的关系，再加上树的递归定义，是一种非常合适动规的框架，树型动态规划就成为动规中很特殊的一种类型。

树形动态规划典型例题

没有上司的晚会

【问题描述】

有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。

已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

【输入：】

第1行一个整数

接下来

接下来每行两个整数

输入以0 0结束。

【输出】：

一个数，最大的气氛值和。

【样例输入】

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

树形动态规划样例输出

5

【分析】

如上例，上司与小兵之间的关系构成一棵树。

5

| \

3 4

| \ | \

1 2 6 7

又是求最优解，并且每一个节点的取舍关乎到全局 因此，此题可用树形动态规划

我们可用

C ：

#include
 
  
using namespace std;
int main()
{
intn,qf[201],f[201][2],shs[201],xb[201][201],shu[201][201],x,s,maxc,j,k,a,b,l,i;//qf存储每个人的气氛值，shs存储每个人的上司，xb存储每个人的下属，shu存储构成的树,maxc存储最大层数
cin>>n;
for(i=0;i<=n;i  )
{
xb[i][0]=0;
shs[i]=0;
}
for(i=1;i<=n;i  )cin>>qf[i];
l=1;
k=1;
while(l!=0||k!=0)
{
cin>>l>>k;
shs[l]=k;
xb[k][0]  ;
xb[k][xb[k][0]]=l;
}
maxc=0;
for(i=1;i<=n;i  )
{
x=i;
s=1;
while(shs[x]!=0)
{
x=shs[x];
s=s 1;
}
shu[s][0]  ;
shu[s][shu[s][0]]=i;
if(s>maxc)maxc=s;
}//建树,maxc存储最大层数
for(i=maxc;i>=1;i--)
for(j=1;j<=shu[i][0];j  )
{
if(xb[shu[i][j]][0]==0)
{
f[shu[i][j]][0]=0;
f[shu[i][j]][1]=qf[shu[i][j]];
}
else
{
f[shu[i][j]][0]=0;
f[shu[i][j]][1]=qf[shu[i][j]];
for(k=1;k<=xb[shu[i][j]][0];k  )
{
a=f[xb[shu[i][j]][k]][0];
b=f[xb[shu[i][j]][k]][1];
f[shu[i][j]][1] =a;
if(b>a)a=b;
f[shu[i][j]][0] =a;
}//动态转移方程
}
}
s=0;
for(i=1;i<=shu[1][0];i  )
{
a=f[shu[1][i]][0];
b=f[shu[1][i]][1];
if(a
   
   
大家看到，树形动态规划基本上可以分为2个部分，一个是建树，另一个就是动态规划，一个好的数据结构，能使你编程非常容易，这也是树形动态规划的难点之一 
   

   pascal：
   
type
link=^node;
node=record
s:longint;
next:link;
end;
constmaxn=100;
var
r:array[1..maxn]oflongint;{存储每个人的搞笑指数}
sum:array[1..maxn,0..1]oflongint;
son:array[1..maxn]oflink;{记录指向儿子结点的指针}
n,root:longint;
i,a,b:longint;
p:link;
functionmax(a,b:longint):longint;
beginifa>bthenexit(a)elseexit(b);end;
procedurecalc(k:longint);{k是根结点}
var
p:link;
i:longint;
begin
sum[k][0]:=0;{初值为0}
sum[k][1]:=0;
p:=son[k];{取结点k的孩子结点}
whilep<>nildo
begin
i:=p^.s;
calc(i);{递归调用此过程，计算以i为根结点的最大搞笑指数}
inc(sum[k][0],max(sum[i][0],sum[i][1]));
inc(sum[k][1],sum[i][0]);
p:=p^.next;{算兄弟}
end;
inc(sum[k][1],r[k]);
end;
begin
read(n);
fori:=1tondo{读入每个结点的搞笑指数}
read(r[i]);
fori:=1ton-1do{n个结点的相互连通的树共有n-1条边}
begin
read(a,b);{b是a的上级}
inc(root,a);{对儿子结点的编号求和}
new(p);{以孩子兄弟表示法来存储树的结构}
p^.s:=a;
p^.next:=son[b];{数组son的初值应为nil}
son[b]:=p;
end;
root:=(n*(n 1)div2)-root;{计算出根结点的编号}
calc(root);
writeln(max(sum[root][0],sum[root][1]));
end.
2100433B