樹形動態規劃問題可以分解成若干相互聯繫的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
基本介紹
- 中文名：樹形動態規劃
- 含義：最最佳化概念
- 用途：使整個活動的總體效果達到最優
- 性質：規劃檔案
樹形動態規劃,階段,狀態,決策,策略,狀態轉移方程,目標函式與最最佳化概念,典型例題,樣例輸出,
樹形動態規劃
動態規劃就是解決多階段決策最最佳化問題的一種思想方法。
階段
將所給問題的過程，按時間或空間特徵分解成若干相互聯繫的階段，以便按次序去求每階段的解。
狀態
各階段開始時的客觀條件叫做狀態。
決策
當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。
策略
由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。
狀態轉移方程
前一階段的終點就是後一階段的起點，前一階段的決策選擇導出了後一階段的狀態，這種關係描述了由k階段到k+1階段狀態的演變規律，稱為狀態轉移方程。
目標函式與最最佳化概念
目標函式是衡量多階段決策過程優劣的準則。最最佳化概念是在一定條件下找到一個途徑，經過按題目具體性質所確定的運算以後，使全過程的總效益達到最優。
大多數動規都是在一維二維這種規則的背景下的，可以解決的問題比較局限，而樹作為一種特殊的圖，可以描述比較複雜的關係，再加上樹的遞歸定義，是一種非常合適動規的框架，樹型動態規劃就成為動規中很特殊的一種類型。
典型例題
沒有上司的晚會等
【問題描述】
有個公司要舉行一場晚會。為了讓到會的每個人不受他的直接上司約束而能玩得開心，公司領導決定：如果邀請了某個人，那么一定不會再邀請他的直接的上司，但該人的上司的上司，上司的上司的上司……都可以邀請。已知每個人最多有唯一的一個上司。
已知公司的每個人參加晚會都能為晚會增添一些氣氛，求一個邀請方案，使氣氛值的和最大。
【輸入：】
第1行一個整數N（1<=N<=6000）表示公司的人數。
接下來N行每行一個整數。第i行的數表示第i個人的氣氛值x（-128<=x<=127）。
接下來每行兩個整數L，K。表示第K個人是第L個人的上司。
輸入以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
又是求最優解，並且每一個節點的取捨關乎到全局 因此，此題可用樹形動態規劃
我們可用f[v][0]存儲不選編號為V的節點的最優解，f[v][1]存儲選編號為V的節點的最優解
#include<iostream>#include<cstdlib>using namespace std;int main(){ int n,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<b)a=b; s=s+a; }//從頂頭上司那裡擇優選擇 cout<<s<<endl; system("pause"); return0;}大家看到，樹形動態規劃基本上可以分為2個部分，一個是建樹，另一個就是動態規劃，一個好的數據結構，能使你編程非常容易，這也是樹形動態規劃的難點之一
pascal:
typelink = ^node;node = records: longint;next: link;end;const maxn=100;varr:array[1..maxn]of longint; {存儲每個人的搞笑指數}sum:array[1..maxn, 0..1]of longint;son:array[1..maxn]of link; {記錄指向兒子結點的指針}n,root: longint;i,a,b:longint;p:link;function max(a,b:longint):longint;begin if a>b then exit(a) else exit(b);end;procedure calc(k: longint); {k是根結點}varp: link;i: longint;beginsum[k][0]:=0; {初值為0}sum[k][1]:=0;p:=son[k]; {取結點k的孩子結點}while p<>nil dobegini:=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;beginread(n);for i:=1 to n do {讀入每個結點的搞笑指數}read(r[i]);for i:=1 to n-1 do {n個結點的相互連通的樹共有n-1條邊}beginread(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) div 2)-root; {計算出根結點的編號}calc(root);writeln(max(sum[root][0], sum[root][1]));end. 