動態規劃演算法的典型應用

1. 動態規劃的應用

記憶化
給你一個數字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出從第一層到最後一層的一條路,使得所經過的權值之和最小或者最大.
無論對於新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態轉移方程：
f[i][j]=a[i][j] + min{f[i+1][j]，f[i+1][j+1]}(a[i][j]表示當前狀態,f[i][j]表示指標函數)
對於動態規劃演算法解決這個問題，我們根據狀態轉移方程和狀態轉移方向，比較容易地寫出動態規劃的循環表示方法。但是，當狀態和轉移非常復雜的時候，也許寫出循環式的動態規劃就不是那麼簡單了。
解決方法：
我們嘗試從正面的思路去分析問題，如上例，不難得出一個非常簡單的遞歸函數: intf(inti,intj,int(*a)[4]){intf1,f2,tmp=0,k;if(i==0||j==0)returna[0][0];if(j==i){for(k=0;k<=i;k++)tmp+=a[k][k];returntmp;}f1=f(i-1,j,a);f2=f(i-1,j-1,a);if(f1<f2)returnf2+a[i][j];elsereturnf1+a[i][j];}顯而易見，這個演算法就是最簡單的搜索演算法。時間復雜度為2^n，明顯是會超時的。分析一下搜索的過程，實際上，很多調用都是不必要的，也就是把產生過的最優狀態，又產生了一次。為了避免浪費，很顯然，我們存放一個opt數組：Opt[i, j] - 每產生一個f(i, j)，將f(i, j)的值放入opt中，以後再次調用到f(i, j)的時候，直接從opt[i, j]來取就可以了。於是動態規劃的狀態轉移方程被直觀地表示出來了，這樣節省了思維的難度，減少了編程的技巧，而運行時間只是相差常數的復雜度，避免了動態規劃狀態轉移先後的問題，而且在相當多的情況下，遞歸演算法能更好地避免浪費，在比賽中是非常實用的。
並且記憶搜索占的內存相對來說較少。
計算核心片段： for(inti=n-1;i>=1;--i)//從倒數第二行開始{for(intj=1;j<=i;j++){if(a[i+1][j][1]>a[i+1][j+1][1])//左邊大{a[i][j][2]=0;//選擇左邊a[i][j][1]+=a[i+1][j][1];}else//右邊大{a[i][j][2]=1;//選擇右邊a[i][j][1]+=a[i+1][j+1][1];}練習題
USACO2.2 Subset Sums
題目如下：
對於從1到N的連續整數集合，能劃分成兩個子集合，且保證每個集合的數字和是相等的。
舉個例子，如果N=3，對於{1，2，3}能劃分成兩個子集合，他們每個的所有數字和是相等的：
{3}and {1,2}
這是唯一一種分法（交換集合位置被認為是同一種劃分方案，因此不會增加劃分方案總數）
如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發的子集合各數字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
給出N，你的程序應該輸出劃分方案總數，如果不存在這樣的劃分方案，則輸出0。程序不能預存結果直接輸出。
PROGRAM NAME: subset
INPUT FORMAT
輸入文件只有一行，且只有一個整數N
SAMPLE INPUT (file subset . in)
7
OUTPUT FORMAT
輸出劃分方案總數，如果不存在則輸出0。
SAMPLE OUTPUT (file subset.out)
4
參考程序如下（C++語言）： #include<fstream>usingnamespacestd;constunsignedintMAX_SUM=1024;intn;unsignedlonglongintdyn[MAX_SUM];ifstreamfin(subset.in);ofstreamfout(subset.out);intmain(){fin>>n;fin.close();ints=n*(n+1);if(s%4){fout<<0<<endl;fout.close();return0;}s/=4;inti,j;dyn[0]=1;for(i=1;i<=n;i++)for(j=s;j>=i;j--)if(j-i>0){dyn[j]+=dyn[j-i];}fout<<(dyn[s]/2)<<endl;fout.close();return0;}USACO2.3LongestPrefix題目如下：
在生物學中，一些生物的結構是用包含其要素的大寫字母序列來表示的。生物學家對於把長的序列分解成較短的（稱之為元素的）序列很感興趣。
如果一個集合 P 中的元素可以通過並運算（允許重復；並，即∪，相當於 Pascal 中的 「+」 運算符）組成一個序列 S ，那麼我們認為序列 S 可以分解為 P 中的元素。並不是所有的元素都必須出現。舉個例子，序列 ABABACABAAB 可以分解為下面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個字元稱作 S 中長度為 K 的前綴。設計一個程序，輸入一個元素集合以及一個大寫字母序列，計算這個序列最長的前綴的長度。
PROGRAM NAME: prefix
INPUT FORMAT
輸入數據的開頭包括 1..200 個元素（長度為 1..10 ）組成的集合，用連續的以空格分開的字元串表示。字母全部是大寫，數據可能不止一行。元素集合結束的標志是一個只包含一個 「.」 的行。集合中的元素沒有重復。接著是大寫字母序列 S ，長度為 1..200,000 ，用一行或者多行的字元串來表示，每行不超過 76 個字元。換行符並不是序列 S 的一部分。
SAMPLE INPUT (file prefix. in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，輸出一個整數，表示 S 能夠分解成 P 中元素的最長前綴的長度。
SAMPLE OUTPUT (file prefix.out)
11
示常式序如下：
#include <stdio.h>
#define MAXP 200
#define MAXL 10
char prim[MAXP+1][MAXL+1];
int nump;
int start[200001];
char data[200000];
int ndata;
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv,lv2, lv3;
if ((fin = fopen(prim. in, r)) == NULL)
{
perror (fopen fin);
exit(1);
}
if((fout = fopen(prim.out, w)) == NULL)
{
perror (fopen fout);
exit(1);
}
while (1)
{
fscanf (fin, %s, prim[nump]);
if (prim[nump][0] != '.')
nump++;
else
break;
}
ndata = 0;
while (fscanf (fin, %s, data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{
best = lv;
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] == data[lv+lv3]; lv3++)
if (!prim[lv2][lv3])
start[lv + lv3] = 1;
}
}
if (start[ndata])
best = ndata;
fprintf (fout, %i , best);
return 0;
}
動態規劃作為一種重要的信息學競賽演算法，具有很強的靈活性。以上提供的是一些入門練習題，深入的學習還需要逐步積累經驗。
解決0-1背包問題時使用動態規劃的實現（c++）
#include <stdio.h>
typedef struct Object{
int weight;
int value; // float rate;
}
Object;
Object * array; //用來存儲物體信息的數組
int num; //物體的個數
int container; //背包的容量
int ** dynamic_table; //存儲動態規劃表
bool * used_table; //存儲物品的使用情況
//ouput the table of dynamic programming, it's for detection
void print_dynamic_table(){
printf(動態規劃表如下所示: );
/* for(int j=0; j<=container; j++) printf(%d ,j); printf( );*/
for(int i=1; i<=num; i++) {
for(int j=0; j<=container; j++)
printf(%d ,dynamic_table[i][j]);
printf( );
}
}
//列印動態規劃表
void print_array(){
for(int i=1; i<=num; i++)
printf(第%d個物品的重量和權重:%d %d ,i,array[i].weight,array[i].value);
}
//列印輸入的物品情況//插入排序，按rate=value/weight由小到大排//動態規劃考慮了所有情況，所以可以不用排序
/*void sort_by_rate(){
for(int i=2; i<=num; i++) {
Object temp=array[i];
for(int j=i-1; j>=1; j--)
if(array[j].rate>temp.rate)
array[j+1]=array[j];
else break;
array[j+1]=temp;
}}*/
void print_used_object(){
printf(所使用的物品如下所示: );
for(int i=1; i<=num; i++)
if(used_table[i]==1)
printf(%d-%d , array[i].weight, array[i].value);
}
//列印物品的使用情況
/* 做測試時使用
void print_used_table(bool * used_table){
printf(used table as follows: );
for(int i=1; i<=num; i++)
printf(object %d is %d, i, used_table[i]);
}*/
void init_problem(){
printf(輸入背包的容量: );
scanf(%d, &container);
printf(輸入物品的個數: );
scanf(%d, &num);
array=new Object[num+1];
printf(輸入物品的重量和價值, 格式如：4-15 );
for(int i=1; i<=num; i++) {
char c;
scanf(%d%c%d, &array[i].weight, &c, &array[i].value);
// array[i].rate=array[i].value/array[i].weight;
}
print_array();
}
//對物體的使用情況進行回查
void trace_back(){
int weight=container;
used_table=new bool[num+1];
for(int i=1; i<=num; i++) used_table[i]=0;
//initalize the used_table to be non-used
for(int j=1; j<num; j++) {
//說明物品j被使用
if(dynamic_table[j][weight]!=dynamic_table[j+1][weight]) {
weight-=array[j].weight;
used_table[j]=1;
}
// print_used_table(used_table);
}
//檢測第num個物品是否被使用
if(weight>=array[num].weight)
used_table[num]=1;
}
void dynamic_programming(){
dynamic_table=new int * [num+1];
for(int k=1; k<=num; k++)
dynamic_table[k]=new int[container+1];
//dynamic_programming table
//為二維動態規劃表分配內存
for(int m=1; m<num; m++)
for(int n=0; n<=container; n++)
dynamic_table[m][n]=0;
int temp_weight=array[num].weight;
for(int i=0; i<=container; i++)
dynamic_table[num][i]=i<temp_weight?0:array[num].value;
//初始化動態規劃表
for(int j=num-1; j>=1; j--) {
temp_weight=array[j].weight;
int temp_value=array[j].value;
for(int k=0; k<=container; k++)
if(k>=temp_weight && dynamic_table[j+1][k] < dynamic_table[j+1][k-temp_weight]+temp_value)
dynamic_table[j][k]=dynamic_table[j+1][k-temp_weight]+temp_value;
else dynamic_table[j][k]=dynamic_table[j+1][k];
}//構建動態規劃表
print_dynamic_table();//列印動態規劃表
}
void main(){
init_problem();
dynamic_programming();
trace_back();
print_used_object();
}

2. 動態規劃演算法的妙用

學動態規劃可以先學一些遞推，關於動態規劃的材料網上太多了！理解動態規劃的重點理解從小到大思想，哪些狀態是要用到的先算出來，避免重復計算！

3. 什麼是動態規劃演算法，常見的動態規劃問題分析與求解

動態規劃的題都是可以分出階段的，比如背包問題可以由前i種物品的情況推導出前i+1種物品。 很多動態規劃都是要求最優化某個值，有最優子結構性質，它的邏輯就是：要我求出前i+1種物品的最優值，

4. 求「動態規劃演算法」在生物信息學中的應用一題

你的題意講的不是很清楚
但我大概猜到是一個什麼模型了
初中學過的動態規劃經典模型
就是 LCS（最長公共子序列） 你可以自己網路一下
主要是因為你題目描述不清，我不能幫你更多了
滿意請採納謝謝！

5. 動態規劃的典型應用領域是 ,其特點是,快考試了，急，如果需要會適當增加懸賞

典型應用領域是解決多階段決策過程。多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
動態規劃的特點：
所給問題的過程，按時間或空間特徵分解成若干相互聯系的階段，以便按次序去求每階段的解。
階段之間通過狀態和狀態轉移進行相互聯系。

6. 關於動態規劃演算法，哪位可以講一下自己心得體會

動態規劃的特點及其應用
安徽 張辰
動態規劃 階段

動態規劃是信息學競賽中的常見演算法，本文的主要內容就是分析它的特點。
文章的第一部分首先探究了動態規劃的本質，因為動態規劃的特點是由它的本質所決定的。第二部分從動態規劃的設計和實現這兩個角度分析了動態規劃的多樣性、模式性、技巧性這三個特點。第三部分將動態規劃和遞推、搜索、網路流這三個相關演算法作了比較，從中探尋動態規劃的一些更深層次的特點。
文章在分析動態規劃的特點的同時，還根據這些特點分析了我們在解題中應該怎樣利用這些特點，怎樣運用動態規劃。這對我們的解題實踐有一定的指導意義。

動態規劃是編程解題的一種重要的手段，在如今的信息學競賽中被應用得越來越普遍。最近幾年的信息學競賽，不分大小，幾乎每次都要考察到這方面的內容。因此，如何更深入地了解動態規劃，從而更為有效地運用這個解題的有力武器，是一個值得深入研究的問題。
要掌握動態規劃的應用技巧，就要了解它的各方面的特點。首要的，是要深入洞悉動態規劃的本質。
§1動態規劃的本質
動態規劃是在本世紀50年代初，為了解決一類多階段決策問題而誕生的。那麼，什麼樣的問題被稱作多階段決策問題呢？
§1.1多階段決策問題
說到多階段決策問題，人們很容易舉出下面這個例子。
[例1] 多段圖中的最短路徑問題：在下圖中找出從A1到D1的最短路徑。
仔細觀察這個圖不難發現，它有一個特點。我們將圖中的點分為四類（圖中的A、B、C、D），那麼圖中所有的邊都處於相鄰的兩類點之間，並且都從前一類點指向後一類點。這樣，圖中的邊就被分成了三類（AàB、BàC、CàD）。我們需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，並且這條路徑是所有這樣的路徑中的最短者。
從上面的這個例子中，我們可以大概地了解到什麼是多階段決策問題。更精確的定義如下：
多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列[1]。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
從上述的定義中，我們可以明顯地看出，這類問題有兩個要素。一個是階段，一個是決策。
§1.2階段與狀態
階段：將所給問題的過程，按時間或空間特徵分解成若干相互聯系的階段，以便按次序去求每階段的解。常用字母k表示階段變數。[1]
階段是問題的屬性。多階段決策問題中通常存在著若干個階段，如上面的例子，就有A、B、C、D這四個階段。在一般情況下，階段是和時間有關的；但是在很多問題（我的感覺，特別是信息學問題）中，階段和時間是無關的。從階段的定義中，可以看出階段的兩個特點，一是「相互聯系」，二是「次序」。
階段之間是怎樣相互聯系的？就是通過狀態和狀態轉移。
狀態：各階段開始時的客觀條件叫做狀態。描述各階段狀態的變數稱為狀態變數，常用sk表示第k階段的狀態變數，狀態變數sk的取值集合稱為狀態集合，用Sk表示。[1]
狀態是階段的屬性。每個階段通常包含若干個狀態，用以描述問題發展到這個階段時所處在的一種客觀情況。在上面的例子中，行人從出發點A1走過兩個階段之後，可能出現的情況有三種，即處於C1、C2或C3點。那麼第三個階段就有三個狀態S3=。
每個階段的狀態都是由以前階段的狀態以某種方式「變化」而來，這種「變化」稱為狀態轉移（暫不定義）。上例中C3點可以從B1點過來，也可以從B2點過來，從階段2的B1或B2狀態走到階段3的C3狀態就是狀態轉移。狀態轉移是導出狀態的途徑，也是聯系各階段的途徑。
說到這里，可以提出應用動態規劃的一個重要條件。那就是將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的發展，而只能通過當前的這個狀態。換句話說，每個狀態都是「過去歷史的一個完整總結[1]」。這就是無後效性。對這個性質，下文還將會有解釋。
§1.3決策和策略
上面的階段與狀態只是多階段決策問題的一個方面的要素，下面是另一個方面的要素——決策。
決策：當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。表示決策的變數，稱為決策變數，常用uk(sk)表示第k階段當狀態為sk時的決策變數。在實際問題中，決策變數的取值往往限制在一定范圍內，我們稱此范圍為允許決策集合。常用Dk(sk)表示第k階段從狀態sk出發的允許決策集合。顯然有uk(sk) ?Dk(sk)。[1]
決策是問題的解的屬性。決策的目的就是「確定下一階段的狀態」，還是回到上例，從階段2的B1狀態出發有三條路，也就是三個決策，分別導向階段3的C1、C2、C3三個狀態，即D2(B1)=。
有了決策，我們可以定義狀態轉移：動態規劃中本階段的狀態往往是上一階段和上一階段的決策結果，由第k段的狀態sk和本階段的決策uk確定第k+1段的狀態sk+1的過程叫狀態轉移。狀態轉移規律的形式化表示sk+1=Tk(sk,uk)稱為狀態轉移方程。
這樣看來，似乎決策和狀態轉移有著某種聯系。我的理解，狀態轉移是決策的目的，決策是狀態轉移的途徑。
各段決策確定後，整個問題的決策序列就構成一個策略，用p1,n=表示。對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最有效果的策略就是最優策略。[1]
說到這里，又可以提出運用動態規劃的一個前提。即這個過程的最優策略應具有這樣的性質：無論初始狀態及初始決策如何，對於先前決策所形成的狀態而言，其以後的所有決策應構成最優策略[1]。這就是最優化原理。簡言之，就是「最優策略的子策略也是最優策略」。
§1.4最優化原理與無後效性
這里，我把最優化原理定位在「運用動態規劃的前提」。這是因為，是否符合最優化原理是一個問題的本質特徵。對於不滿足最優化原理的一個多階段決策問題，整體上的最優策略p1,n同任何一個階段k上的決策uk或任何一組階段k1…k2上的子策略pk1,k2都不存在任何關系。如果要對這樣的問題動態規劃的話，我們從一開始所作的劃分階段等努力都將是徒勞的。
而我把無後效性定位在「應用動態規劃的條件」，是因為動態規劃是按次序去求每階段的解，如果一個問題有後效性，那麼這樣的次序便是不合理的。但是，我們可以通過重新劃分階段，重新選定狀態，或者增加狀態變數的個數等手段，來是問題滿足無後效性這個條件。說到底，還是要確定一個「序」。
在信息學的多階段決策問題中，絕大部分都是能夠滿足最優化原理的，但它們往往會在後效性這一點上來設置障礙。所以在解題過程中，我們會特別關心「序」。對於有序的問題，就會考慮到動態規劃；對於無序的問題，也會想方設法來使其有序。
§1.5最優指標函數和規劃方程
最優指標函數：用於衡量所選定策略優劣的數量指標稱為指標函數，最優指標函數記為fk(sk)，它表示從第k段狀態sk採用最優策略p*k,n到過程終止時的最佳效益值[1]。
最優指標函數其實就是我們真正關心的問題的解。在上面的例子中，f2(B1)就表示從B1點到終點D1點的最短路徑長度。我們求解的最終目標就是f1(A1)。
最優指標函數的求法一般是一個從目標狀態出發的遞推公式，稱為規劃方程：

其中sk是第k段的某個狀態，uk是從sk出發的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態sk+1，g(x,uk)是定義在數值x和決策uk上的一個函數，而函數opt表示最優化，根據具體問題分別表為max或min。
，稱為邊界條件。
上例中的規劃方程就是：

邊界條件為
這里是一種從目標狀態往回推的逆序求法，適用於目標狀態確定的問題。在我們的信息學問題中，也有很多有著確定的初始狀態。當然，對於初始狀態確定的問題，我們也可以採用從初始狀態出發往前推的順序求法。事實上，這種方法對我們來說要更為直觀、更易設計一些，從而更多地出現在我們的解題過程中。
我們本節所討論的這些理論雖然不是本文的主旨，但是卻對下面要說的動態規劃的特點起著基礎性的作用。
§2動態規劃的設計與實現
上面我們討論了動態規劃的一些理論，本節我們將通過幾個例子中，動態規劃的設計與實現，來了解動態規劃的一些特點。
§2.1動態規劃的多樣性
[例2] 花店櫥窗布置問題（IOI99）試題見附錄
本題雖然是本屆IOI中較為簡單的一題，但其中大有文章可作。說它簡單，是因為它有序，因此我們一眼便可看出這題應該用動態規劃來解決。但是，如何動態規劃呢？如何劃分階段，又如何選擇狀態呢？
<方法1>以花束的數目來劃分階段。在這里，階段變數k表示的就是要布置的花束數目（前k束花），狀態變數sk表示第k束花所在的花瓶。而對於每一個狀態sk，決策就是第k-1束花應該放在哪個花瓶，用uk表示。最優指標函數fk(sk)表示前k束花，其中第k束插在第sk個花瓶中，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
（其中A(i,j)是花束i插在花瓶j中的美學值）
邊界條件 （V是花瓶總數，事實上這是一個虛擬的邊界）
<方法2>以花瓶的數目來劃分階段。在這里階段變數k表示的是要佔用的花瓶數目（前k個花瓶），狀態變數sk表示前k個花瓶中放了多少花。而對於任意一個狀態sk，決策就是第sk束花是否放在第k個花瓶中，用變數uk=1或0來表示。最優指標函數fk(sk)表示前k個花瓶中插了sk束花，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
邊界條件為
兩種劃分階段的方法，引出了兩種狀態表示法，兩種規劃方式，但是卻都成功地解決了問題。只不過因為決策的選擇有多有少，所以演算法的時間復雜度也就不同。[2]
這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規劃方法。有時各種方法所產生的效果是差不多的，但更多的時候，就像我們的例子一樣，兩種方法會在某個方面有些區別。
所以，在用動態規劃解題的時候，可以多想一想是否有其它的解法。對於不同的解法，要注意比較，好的演算法好在哪裡，差一點的演算法差在哪裡。從各種不同演算法的比較中，我們可以更深刻地領會動態規劃的構思技巧。
§2.2動態規劃的模式性
這個可能做過動態規劃的人都有體會，從我們上面對動態規劃的分析也可以看出來。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的，否則問題就無法求解。
選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
確定決策並寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。
寫出規劃方程（包括邊界條件）：在第一部分中，我們已經給出了規劃方程的通用形式化表達式。一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。
動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。大體上的框架如下：
對f1(s1)初始化（邊界條件）
for k?2 to n（這里以順序求解為例）
對每一個sk?Sk
fk(sk)?一個極值（∞或－∞）
對每一個uk(sk)?Dk(sk)
sk-1?Tk(sk,uk)
t?g(fk-1(sk-1),uk)
y t比fk(sk)更優 n
fk(sk)?t
輸出fn(sn)
這個N-S圖雖然不能代表全部，但足可以概括大多數。少數的一些特殊的動態規劃，其實現的原理也是類似，可以類比出來。我們到現在對動態規劃的分析，主要是在理論上、設計上，原因也就在此。
掌握了動態規劃的模式性，我們在用動態規劃解題時就可以把主要的精力放在理論上的設計。一旦設計成熟，問題也就基本上解決了。而且在設計演算法時也可以按部就班地來。
但是「物極必反」，太過拘泥於模式就會限制我們的思維，扼殺優良演算法思想的產生。我們在解題時，不妨發揮一下創造性，去突破動態規劃的實現模式，這樣往往會收到意想不到的效果。[3]
§2.3動態規劃的技巧性
上面我們所說的動態規劃的模式性，主要指的是實現方面。而在設計方面，雖然它較為嚴格的步驟性，但是它的設計思想卻是沒有一定的規律可循的。這就需要我們不斷地在實踐當中去掌握動態規劃的技巧，下面僅就一個例子談一點我自己的體會。
[例3] 街道問題：在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。
這是一道簡單而又典型的動態規劃題，許多介紹動態規劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：

按照圖中的虛線來劃分階段，即階段變數k表示走過的步數，而狀態變數sk表示當前處於這一階段上的哪一點（各點所對應的階段和狀態已經用ks在地圖上標明）。這時的模型實際上已經轉化成了一個特殊的多段圖。用決策變數uk=0表示向右走，uk=1表示向上走，則狀態轉移方程如下：

（這里的row是地圖豎直方向的行數）
我們看到，這個狀態轉移方程需要根據k的取值分兩種情況討論，顯得非常麻煩。相應的，把它代入規劃方程而付諸實現時，演算法也很繁。因而我們在實現時，一般是不會這么做的，而代之以下面方法：
將地圖中的點規則地編號如上，得到的規劃方程如下：

（這里Distance表示相鄰兩點間的邊長）
這樣做確實要比上面的方法簡單多了，但是它已經破壞了動態規劃的本來面目，而不存在明確的階段特徵了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那麼它的「狀態轉移」就不全是在兩個階段之間進行的了。
也許這沒什麼大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，並且要求兩條路徑的總長度最短。這時，再用這種「簡單」的方法就不太好辦了。
如果非得套用這種方法的話，則最優指標函數就需要有四維的下標，並且難以處理兩條路徑「不能重疊」的問題。
而我們回到原先「標准」的動態規劃法，就會發現這個問題很好解決，只需要加一維狀態變數就成了。即用sk=(ak,bk)分別表示兩條路徑走到階段k時所處的位置，相應的，決策變數也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態轉移時將兩條路徑分別考慮：

在寫規劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數：

從這個例子中可以總結出設計動態規劃演算法的一個技巧：狀態轉移一般是在相鄰的兩個階段之間（有時也可以在不相鄰的兩個階段間），但是盡量不要在同一個階段內進行。
動態規劃是一種很靈活的解題方法，在動態規劃演算法的設計中，類似的技巧還有很多。要掌握動態規劃的技巧，有兩條途徑：一是要深刻理解動態規劃的本質，這也是我們為什麼一開始就探討它的本質的原因；二是要多實踐，不但要多解題，還要學會從解題中探尋規律，總結技巧。
§3動態規劃與一些演算法的比較
動態規劃作為諸多解題方法中的一種，必然和其他一些演算法有著諸多聯系。從這些聯系中，我們也可以看出動態規劃的一些特點。
§3.1動態規劃與遞推
——動態規劃是最優化演算法
由於動態規劃的「名氣」如此之大，以至於很多人甚至一些資料書上都往往把一種與動態規劃十分相似的演算法，當作是動態規劃。這種演算法就是遞推。實際上，這兩種演算法還是很容易區分的。
按解題的目標來分，信息學試題主要分四類：判定性問題、構造性問題、計數問題和最優化問題。我們在競賽中碰到的大多是最優化問題，而動態規劃正是解決最優化問題的有力武器，因此動態規劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態規劃在這兩個方面的聯系。
[例4] mod 4 最優路徑問題：在下圖中找出從第1點到第4點的一條路徑，要求路徑長度mod 4的余數最小。
這個圖是一個多段圖，而且是一個特殊的多段圖。雖然這個圖的形式比一般的多段圖要簡單，但是這個最優路徑問題卻不能用動態規劃來做。因為一條從第1點到第4點的最優路徑，在它走到第2點、第3點時，路徑長度mod 4的余數不一定是最小，也就是說最優策略的子策略不一定最優——這個問題不滿足最優化原理。
但是我們可以把它轉換成判定性問題，用遞推法來解決。判斷從第1點到第k點的長度mod 4為sk的路徑是否存在，用fk(sk)來表示，則遞推公式如下：
（邊界條件）

（這里lenk,i表示從第k-1點到第k點之間的第i條邊的長度，方括弧表示「或(or)」運算）
最後的結果就是可以使f4(s4)值為真的最小的s4值。
這個遞推法的遞推公式和動態規劃的規劃方程非常相似，我們在這里借用了動態規劃的符號也就是為了更清楚地顯示這一點。其實它們的思想也是非常相像的，可以說是遞推法借用了動態規劃的思想解決了動態規劃不能解決的問題。
有的多階段決策問題（像這一題的階段特徵就很明顯），由於不能滿足最優化原理等使用動態規劃的先決條件，而無法應用動態規劃。在這時可以將最優指標函數的值當作「狀態」放到下標中去，從而變最優化問題為判定性問題，再借用動態規劃的思想，用遞推法來解決問題。
§3.2動態規劃與搜索
——動態規劃是高效率、高消費演算法
同樣是解決最優化問題，有的題目我們採用動態規劃，而有的題目我們則需要用搜索。這其中有沒有什麼規則呢？
我們知道，撇開時空效率的因素不談，在解決最優化問題的演算法中，搜索可以說是「萬能」的。所以動態規劃可以解決的問題，搜索也一定可以解決。
把一個動態規劃演算法改寫成搜索是非常方便的，狀態轉移方程、規劃方程以及邊界條件都可以直接「移植」，所不同的只是求解順序。動態規劃是自底向上的遞推求解，而搜索則是自頂向下的遞歸求解（這里指深度搜索，寬度搜索類似）。
反過來，我們也可以把搜索演算法改寫成動態規劃。狀態空間搜索實際上是對隱式圖中的點進行枚舉，這種枚舉是自頂向下的。如果把枚舉的順序反過來，變成自底向上，那麼就成了動態規劃。（當然這里有個條件，即隱式圖中的點是可排序的，詳見下一節。）
正因為動態規劃和搜索有著求解順序上的不同，這也造成了它們時間效率上的差別。在搜索中，往往會出現下面的情況：
對於上圖(a)這樣幾個狀態構成的一個隱式圖，用搜索演算法就會出現重復，如上圖(b)所示，狀態C2被搜索了兩次。在深度搜索中，這樣的重復會引起以C2為根整個的整個子搜索樹的重復搜索；在寬度搜索中，雖然這樣的重復可以立即被排除，但是其時間代價也是不小的。而動態規劃就沒有這個問題，如上圖(c)所示。
一般說來，動態規劃演算法在時間效率上的優勢是搜索無法比擬的。（當然對於某些題目，根本不會出現狀態的重復，這樣搜索和動態規劃的速度就沒有差別了。）而從理論上講，任何拓撲有序（現實中這個條件常常可以滿足）的隱式圖中的搜索演算法都可以改寫成動態規劃。但事實上，在很多情況下我們仍然不得不採用搜索演算法。那麼，動態規劃演算法在實現上還有什麼障礙嗎？
考慮上圖(a)所示的隱式圖，其中存在兩個從初始狀態無法達到的狀態。在搜索演算法中，這樣的兩個狀態就不被考慮了，如上圖(b)所示。但是動態規劃由於是自底向上求解，所以就無法估計到這一點，因而遍歷了全部的狀態，如上圖(c)所示。
一般說來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的事搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。
如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化演算法。記憶化演算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。
§3.3動態規劃與網路流
——動態規劃是易設計易實現演算法
由於圖的關系復雜而無序，一般難以呈現階段特徵（除了特殊的圖如多段圖，或特殊的分段方法如Floyd），因此動態規劃在圖論中的應用不多。但有一類圖，它的點卻是有序的，這就是有向無環圖。
在有向無環圖中，我們可以對點進行拓撲排序，使其體現出有序的特徵，從而據此劃分階段。在有向無還圖中求最短路徑的演算法[4]，已經體現出了簡單的動態規劃思想。但動態規劃在圖論中還有更有價值的應用。下面先看一個例子。
[例6] N個人的街道問題：在街道問題（參見例3）中，若有N個人要從左下角走向右上角，要求他們走過的邊的總長度最大。當然，這里每個人也只能向右或向上走。下面是一個樣例，左圖是從出發地到目的地的三條路徑，右圖是他們所走過的邊，這些邊的總長度為5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
這個題目是對街道問題的又一次擴展。仿照街道問題的解題方法，我們仍然可以用動態規劃來解決本題。不過這一次是N個人同時走，狀態變數也就需要用N維來表示，。相應的，決策變數也要變成N維，uk=(uk,1,uk,2,…,uk,N)。狀態轉移方程不需要做什麼改動：

在寫規劃方程時，需要注意在第k階段，N條路徑所走過的邊的總長度的計算，在這里我就用gk(sk,uk)來表示了：

邊界條件為
可見將原來的動態規劃演算法移植到這個問題上來，在理論上還是完全可行的。但是，現在的這個動態規劃演算法的時空復雜度已經是關於N的指數函數，只要N稍微大一點，這個演算法就不可能實現了。
下面我們換一個思路，將N條路徑看成是網路中一個流量為N的流，這樣求解的目標就是使這個流的費用最大。但是本題又不同於一般的費用流問題，在每一條邊e上的流費用並不是流量和邊權的乘積 ，而是用下式計算：

為了使經典的費用流演算法適用於本題，我們需要將模型稍微轉化一下：
如圖，將每條邊拆成兩條。拆開後一條邊上有權，但是容量限制為1；另一條邊沒有容量限制，但是流過這條邊就不能計算費用了。這樣我們就把問題轉化成了一個標準的最大費用固定流問題。
這個演算法可以套用經典的最小費用最大流演算法，在此就不細說了。（參見附錄中的源程序）
這個例題是我仿照IOI97的「障礙物探測器」一題[6]編出來的。「障礙物探測器」比這一題要復雜一些，但是基本思想是相似的。類似的題目還有99年冬令營的「迷宮改造」[7]。從這些題目中都可以看到動態規劃和網路流的聯系。
推廣到一般情況，任何有向無環圖中的費用流問題在理論上說，都可以用動態規劃來解決。對於流量為N（如果流量不固定，這個N需要事先求出來）的費用流問題，用N維的變數sk=(sk,1,sk,2,…,sk,N)來描述狀態，其中sk,i?V(1￡i￡N)。相應的，決策也用N維的變數uk=(uk,1,uk,2,…,uk,N)來表示，其中uk,i?E(sk,i)(1￡i￡N)，E(v)表示指向v的弧集。則狀態轉移方程可以這樣表示：
sk-1,i = uk,i的弧尾結點
規劃方程為
邊界條件為
但是，由於動態規劃演算法是指數級演算法，因而在實現中的局限性很大，僅可用於一些N非常小的題目。然而在競賽解題中，比如上面說到的IOI97以及99冬令營測試時，我們使用動態規劃的傾向性很明顯（「障礙物探測器」中，我們用的是貪心策略，求N=1或N=2時的局部最優解[8]）。這主要有兩個原因：
一． 雖然網路流有著經典的演算法，但是在競賽中不可能出現經典的問題。如果要運用網路流演算法，則需要經過一番模型轉化，有時這個轉化還是相當困難的。因此在演算法的設計上，靈活巧妙的動態規劃演算法反而要更為簡單一些。
二． 網路流演算法實現起來很繁，這是被人們公認的。因而在競賽的緊張環境中，實現起來有一定模式的動態規劃演算法又多了一層優勢。
正由於動態規劃演算法在設計和實現上的簡便性，所以在N不太大時，也就是在動態規劃可行的情況下，我們還是應該盡量運用動態規劃。
§4結語
本文的內容比較雜，是我幾年來對動態規劃的參悟理解、心得體會。雖然主要的篇幅講的都是理論，但是根本的目的還是指導實踐。
動態規劃，據我認為，是當今信息學競賽中最靈活、也最能體現解題者水平的一類解題方法。本文內容雖多，不能涵蓋動態規劃之萬一。「紙上得來終覺淺，絕知此事要躬行。」要想真正領悟、理解動態規劃的思想，掌握動態規劃的解題技巧，還需要在實踐中不斷地挖掘、探索。實踐得多了，也就能體會到漸入佳境之妙了。
動態規劃，
演算法之常，
運用之妙，
存乎一心。

7. 動態規劃演算法程序例子

給你導彈攔截的吧：
[問題描述]
某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於30000的正整數，每個數據之間至少有一個空格），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

[輸入輸出樣例]
INPUT：
389 207 155 300 299 170 158 65
OUTPUT：
6（最多能攔截的導彈數）
2（要攔截所有導彈最少要配備的系統數）

[問題分析]
我們先解決第一問。一套系統最多能攔多少導彈，跟它最後攔截的導彈高度有很大關系。假設a[i]表示攔截的最後一枚導彈是第i枚時，系統能攔得的最大導彈數。例如，樣例中a[5]=3，表示：如果系統攔截的最後一枚導彈是299的話，最多可以攔截第1枚（389）、第4枚（300）、第5枚（299）三枚導彈。顯然，a[1]~a[8]中的最大值就是第一問的答案。關鍵是怎樣求得a[1]~a[8]。
假設現在已經求得a[1]~a[7]（註：在動態規劃中，這樣的假設往往是很必要的），那麼怎樣求a[8]呢？a[8]要求系統攔截的最後1枚導彈必須是65，也就意味著倒數第2枚被攔截的導彈高度必須不小於65，則符合要求的導彈有389、207、155、300、299、170、158。假如最後第二枚導彈是300，則a[8]=a[4]+1；假如倒數第2枚導彈是299，則a[8]=a[5]+1；類似地，a[8]還可能是a[1]+1、a[2]+1、……。當然，我們現在求得是以65結尾的最多導彈數目，因此a[8]要取所有可能值的最大值，即a[8]=max{a[1]+1,a[2]+1,……，a[7]+1}=max{a[i]}+1 (i=1..7)。
類似地，我們可以假設a[1]~a[6]為已知，來求得a[7]。同樣，a[6]、a[5]、a[4]、a[3]、a[2]也是類似求法，而a[1]就是1，即如果系統攔截的最後1枚導彈是389，則只能攔截第1枚。
這樣，求解過程可以用下列式子歸納：
a[1]=1
a[i]=max{a[j]}+1 （i>1，j=1,2,…,i-1，且j同時要滿足：a[j]>=a[i]）
最後，只需把a[1]~a[8]中的最大值輸出即可。這就是第一問的解法，這種解題方法就稱為「動態規劃」。

第二問比較有意思。由於它緊接著第一問，所以很容易受前面的影響，多次採用第一問的辦法，然後得出總次數，其實這是不對的。要舉反例並不難，比如長為7的高度序列「7 5 4 1 6 3 2」， 最長不上升序列為「7 5 4 3 2」，用多次求最長不上升序列的結果為3套系統；但其實只要2套，分別擊落「7 5 4 1」與「6 3 2」。所以不能用「動態規劃」做，那麼，正確的做法又是什麼呢？
我們的目標是用最少的系統擊落所有導彈，至於系統之間怎麼分配導彈數目則無關緊要，上面錯誤的想法正是承襲了「一套系統盡量多攔截導彈」的思維定勢，忽視了最優解中各個系統攔截數較為平均的情況，本質上是一種貪心演算法，但貪心的策略不對。如果從每套系統攔截的導彈方面來想行不通的話，我們就應該換一個思路，從攔截某個導彈所選的系統入手。
題目告訴我們，已有系統目前的瞄準高度必須不低於來犯導彈高度，所以，當已有的系統均無法攔截該導彈時，就不得不啟用新系統。如果已有系統中有一個能攔截該導彈，我們是應該繼續使用它，還是另起爐灶呢？事實是：無論用哪套系統，只要攔截了這枚導彈，那麼系統的瞄準高度就等於導彈高度，這一點對舊的或新的系統都適用。而新系統能攔截的導彈高度最高，即新系統的性能優於任意一套已使用的系統。既然如此，我們當然應該選擇已有的系統。如果已有系統中有多個可以攔截該導彈，究竟選哪一個呢？當前瞄準高度較高的系統的「潛力」較大，而瞄準高度較低的系統則不同，它能打下的導彈別的系統也能打下，它夠不到的導彈卻未必是別的系統所夠不到的。所以，當有多個系統供選擇時，要選瞄準高度最低的使用，當然瞄準高度同時也要大於等於來犯導彈高度。
解題時用一個數組sys記下當前已有系統的各個當前瞄準高度，該數組中實際元素的個數就是第二問的解答。

[參考程序]
program noip1999_2;
const max=1000;
var i,j,current,maxlong,minheight,select,tail,total:longint;
height,longest,sys:array [1..max] of longint;
line:string;
begin
write('Input test data:');
readln(line); {輸入用字元串}
i:=1;
total:=0; {飛來的導彈數}
while i<=length(line) do {分解出若干個數，存儲在height數組中}
begin
while (i<=length(line)) and (line[i]=' ') do i:=i+1; {過濾空格}
current:=0; {記錄一個導彈的高度}
while (i<=length(line)) and (line[i]<>' ') do {將一個字元串變成數}
begin
current:=current*10+ord(line[i])-ord('0');
i:=i+1
end;
total:=total+1;
height[total]:=current {存儲在height中}
end;
longest[1]:=1; {以下用動態規劃求第一問}
for i:=2 to total do
begin
maxlong:=1;
for j:=1 to i-1 do
begin
if height[i]<=height[j]
then if longest[j]+1>maxlong
then maxlong:=longest[j]+1;
longest[i]:=maxlong {以第i個導彈為結束，能攔截的最多導彈數}
end;
end;
maxlong:=longest[1];
for i:=2 to total do
if longest[i]>maxlong then maxlong:=longest[i];
writeln(maxlong); {輸出第一問的結果}
sys[1]:=height[1]; {以下求第二問}
tail:=1; {數組下標，最後也就是所需系統數}
for i:=2 to total do
begin
minheight:=maxint;
for j:=1 to tail do {找一套最適合的系統}
if sys[j]>height[i] then
if sys[j]<minheight then
begin minheight:=sys[j]; select:=j end;
if minheight=maxint {開一套新系統}
then begin tail:=tail+1; sys[tail]:=height[i] end
else sys[select]:=height[i]
end;
writeln(tail)
end.

[部分測試數據]
輸入1：300 250 275 252 200 138 245
輸出1：
5
2

輸入2：181 205 471 782 1033 1058 1111
輸出2：
1
7

輸入3：465 978 486 476 324 575 384 278 214 657 218 445 123
輸出3：
7
4

輸入4：236 865 858 565 545 445 455 656 844 735 638 652 659 714 845
輸出4：
6
7
夠詳細的吧

8. 什麼是動態規劃如何運用動態規劃解決實際問題

我也不明白，找一下看有用沒。

動態規劃演算法的應用
一、動態規劃的概念
近年來，涉及動態規劃的各種競賽題越來越多，每一年的NOI幾乎都至少有一道題目需要用動態規劃的方法來解決；而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。
要了解動態規劃的概念，首先要知道什麼是多階段決策問題。
1. 多階段決策問題
如果一類活動過程可以分為若干個互相聯系的階段，在每一個階段都需作出決策(採取措施)，一個階段的決策確定以後，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線，則稱它為多階段決策問題。
各個階段的決策構成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應於一個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優策略，使在預定的標准下達到最好的效果.
2．動態規劃問題中的術語
階段：把所給求解問題的過程恰當地分成若干個相互聯系的階段，以便於求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。
在前面的例子中，第一個階段就是點A，而第二個階段就是點A到點B，第三個階段是點B到點C，而第四個階段是點C到點D。
狀態：狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
在前面的例子中，第一個階段有一個狀態即A，而第二個階段有兩個狀態B1和B2，第三個階段是三個狀態C1，C2和C3，而第四個階段又是一個狀態D。
過程的狀態通常可以用一個或一組數來描述，稱為狀態變數。一般，狀態是離散的，但有時為了方便也將狀態取成連續的。當然，在現實生活中，由於變數形式的限制，所有的狀態都是離散的，但從分析的觀點，有時將狀態作為連續的處理將會有很大的好處。此外，狀態可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態維數可以不同。
當過程按所有可能不同的方式發展時，過程各段的狀態變數將在某一確定的范圍內取值。狀態變數取值的集合稱為狀態集合。
無後效性：我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用一個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性。
決策：一個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個數或一組數。不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的范圍稱為允許決策集合。
策略：由每個階段的決策組成的序列稱為策略。對於每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優效果的策略稱為最優策略。
給定k階段狀態變數x(k)的值後，如果這一階段的決策變數一經確定，第k+1階段的狀態變數x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那麼可以把這一關系看成(x(k)，u(k))與x(k+1)確定的對應關系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態轉移規律，稱為狀態轉移方程。
最優性原理:作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，餘下的子策略必然構成「最優子策略」。
最優性原理實際上是要求問題的最優策略的子策略也是最優。讓我們通過對前面的例子再分析來具體說明這一點：從A到D，我們知道，最短路徑是AB1C2D，這些點的選擇構成了這個例子的最優策略，根據最優性原理，這個策略的每個子策略應是最優：AB1C2是A到C2的最短路徑，B1C2D也是B1到D的最短路徑……——事實正是如此，因此我們認為這個例子滿足最優性原理的要求。
[編輯本段]動態規劃練習題
USACO
2.2 Subset Sums
題目如下：
對於從1到N的連續整集合合，能劃分成兩個子集合，且保證每個集合的數字和是相等的。
舉個例子，如果N=3，對於{1，2，3}能劃分成兩個子集合，他們每個的所有數字和是相等的：
{3}and {1,2}
這是唯一一種分發（交換集合位置被認為是同一種劃分方案，因此不會增加劃分方案總數）
如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發的子集合各數字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
給出N，你的程序應該輸出劃分方案總數，如果不存在這樣的劃分方案，則輸出0。程序不能預存結果直接輸出。
PROGRAM NAME: subset
INPUT FORMAT
輸入文件只有一行，且只有一個整數N
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
輸出劃分方案總數，如果不存在則輸出0。
SAMPLE OUTPUT (file subset.out)
4
參考程序如下（c語言）：
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /= 4;
int i, j;
dyn [0] = 1;
for (i = 1; i <= n; i++)
for (j = s; j >= i; j--)
dyn[j] += dyn[j-i];
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
USACO 2.3
Longest Prefix
題目如下：
在生物學中，一些生物的結構是用包含其要素的大寫字母序列來表示的。生物學家對於把長的序列分解成較短的（稱之為元素的）序列很感興趣。
如果一個集合 P 中的元素可以通過串聯（允許重復；串聯，相當於 Pascal 中的 「+」 運算符）組成一個序列 S ，那麼我們認為序列 S 可以分解為 P 中的元素。並不是所有的元素都必須出現。舉個例子，序列 ABABACABAAB 可以分解為下面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個字元稱作 S 中長度為 K 的前綴。設計一個程序，輸入一個元素集合以及一個大寫字母序列，計算這個序列最長的前綴的長度。
PROGRAM NAME: prefix
INPUT FORMAT
輸入數據的開頭包括 1..200 個元素（長度為 1..10 ）組成的集合，用連續的以空格分開的字元串表示。字母全部是大寫，數據可能不止一行。元素集合結束的標志是一個只包含一個 「.」 的行。集合中的元素沒有重復。接著是大寫字母序列 S ，長度為 1..200,000 ，用一行或者多行的字元串來表示，每行不超過 76 個字元。換行符並不是序列 S 的一部分。
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，輸出一個整數，表示 S 能夠分解成 P 中元素的最長前綴的長度。
SAMPLE OUTPUT (file prefix.out)
11
示常式序如下：
#include <stdio.h>
/* maximum number of primitives */
#define MAXP 200
/* maximum length of a primitive */
#define MAXL 10
char prim[MAXP+1][MAXL+1]; /* primitives */
int nump; /* number of primitives */
int start[200001]; /* is this prefix of the sequence expressible? */
char data[200000]; /* the sequence */
int ndata; /* length of the sequence */
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv, lv2, lv3;
if ((fin = fopen("prim.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("prim.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
/* read in primitives */
while (1)
{
fscanf (fin, "%s", prim[nump]);
if (prim[nump][0] != '.') nump++;
else break;
}
/* read in string, one line at a time */
ndata = 0;
while (fscanf (fin, "%s", data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{ /* for each expressible prefix */
best = lv; /* we found a longer expressible prefix! */
/* for each primitive, determine the the sequence starting at
this location matches it */
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
prim[lv2][lv3] == data[lv+lv3]; lv3++)
;
if (!prim[lv2][lv3]) /* it matched! */
start[lv + lv3] = 1; /* so the expanded prefix is also expressive */
}
}
/* see if the entire sequence is expressible */
if (start[ndata]) best = ndata;
fprintf (fout, "%i\n", best);
return 0;
}
USACO 3.1
Score Inflation
題目如下：
我們試著設計我們的競賽以便人們能盡可能的多得分,這需要你的幫助。
我們可以從幾個種類中選取競賽的題目,這里的一個"種類"是指一個競賽題目的集合,解決集合中的題目需要相同多的時間並且能得到相同的分數。
你的任務是寫一個程序來告訴USACO的職員,應該從每一個種類中選取多少題目,使得解決題目的總耗時在競賽規定的時間里並且總分最大。
輸入包括競賽的時間,M(1 <= M <= 10,000)和N,"種類"的數目1 <= N <= 10,000。
後面的每一行將包括兩個整數來描述一個"種類":
第一個整數說明解決這種題目能得的分數(1 <= points <= 10000),第二整數說明解決這種題目所需的時間(1 <= minutes <= 10000)。
你的程序應該確定我們應該從每個"種類"中選多少道題目使得能在競賽的時間中得到最大的分數。
來自任意的"種類"的題目數目可能任何非負數(0或更多)。
計算可能得到的最大分數。
PROGRAM NAME: inflate
INPUT FORMAT
第 1 行: M, N--競賽的時間和題目"種類"的數目。
第 2-N+1 行: 兩個整數:每個"種類"題目的分數和耗時。
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
單獨的一行包括那個在給定的限制里可能得到的最大的分數。
SAMPLE OUTPUT (file inflate.out)
605
{從第2個"種類"中選兩題，第4個"種類"中選三題}
示常式序如下：
#include <fstream.h>
ifstream fin("inflate.in");
ofstream fout("inflate.out");
const short maxm = 10010;
long best[maxm], m, n;
void
main()
{
short i, j, len, pts;
fin >> m >> n;
for (j = 0; j <= m; j++)
best[j] = 0;
for (i = 0; i < n; i++) {
fin >> pts >> len;
for (j = len; j <= m; j++)
if (best[j-len] + pts > best[j])
best[j] = best[j-len] + pts;
}
fout << best[m] << endl; // 由於數組元素不減，末元素最大
}
USACO 3.3
A Game
題目如下：
有如下一個雙人游戲:N(2 <= N <= 100)個正整數的序列放在一個游戲平台上，兩人輪流從序列的兩端取數，取數後該數字被去掉並累加到本玩家的得分中，當數取盡時，游戲結束。以最終得分多者為勝。
編一個執行最優策略的程序，最優策略就是使自己能得到在當前情況下最大的可能的總分的策略。你的程序要始終為第二位玩家執行最優策略。
PROGRAM NAME: game1
INPUT FORMAT
第一行: 正整數N, 表示序列中正整數的個數。
第二行至末尾: 用空格分隔的N個正整數（大小為1-200）。
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
只有一行，用空格分隔的兩個整數: 依次為玩家一和玩家二最終的得分。
SAMPLE OUTPUT (file game1.out)
18 11
參考程序如下：
#include <stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d", &aux);
t = t[i - 1] + aux;
}
fclose (stdin);
}
inline int
min (int x, int y) {
return x > y ? y : x;
}
void
solve () {
int i, l;
for (l = 1; l <= n; l++)
for (i = 1; i + l <= n + 1; i++)
best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
best[(l - 1) % 2]);
}
void writex () {
freopen ("game1.out", "w", stdout);
printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
fclose (stdout);
}
int
main () {
readx ();
solve ();
writex ();
return 0;
}
USACO 3.4
Raucous Rockers
題目如下：
你剛剛得到了流行的「破鑼搖滾」樂隊錄制的尚未發表的N(1 <= N <= 20)首歌的版權。你打算從中精選一些歌曲，發行M(1 <= M <= 20)張CD。每一張CD最多可以容納T(1 <= T <= 20)分鍾的音樂，一首歌不能分裝在兩張CD中。
不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術價值。於是你決定根據以下標准進行選擇：
歌曲必須按照創作的時間順序在CD盤上出現。
選中的歌曲數目盡可能地多。
PROGRAM NAME: rockers
INPUT FORMAT
第一行： 三個整數：N, T, M.
第二行： N個整數，分別表示每首歌的長度，按創作時間順序排列。
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
一個整數，表示可以裝進M張CD盤的樂曲的最大數目。
SAMPLE OUTPUT (file rockers.out)
3
參考程序如下：
#include <stdio.h>
#define MAX 25
int dp[MAX][MAX][MAX], length[MAX];
int
main ()
{
FILE *in = fopen ("rockers.in", "r");
FILE *out = fopen ("rockers.out", "w");
int a, b, c, d, best, numsongs, cdlength, numcds;
fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds);
for (a = 1; a <= numsongs; a++)
fscanf (in, "%d", &length[a]);
best = 0;
for (a = 0; a < numcds; a++)/*當前cd */
for (b = 0; b <= cdlength; b++) /* 已過的時間*/
for (c = 0; c <= numsongs; c++) { /* 上一曲*/
for (d = c + 1; d <= numsongs; d++) { /* 下一曲*/
if (b + length[d] <= cdlength) {
if (dp[a][c] + 1 > dp[a][b + length[d]][d])
dp[a][b + length[d]][d] = dp[a][c] + 1;
}
else {
if (dp[a][c] + 1 > dp[a + 1][length[d]][d])
dp[a + 1][length[d]][d] = dp[a][c] + 1;
}
}
if (dp[a][c] > best)
best = dp[a][c];
}
fprintf (out, "%d\n", best);
return 0;
}
USACO
4.3 Buy Low, Buy Lower
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例, 某幾天的股價是:
天數 1 2 3 4 5 6 7 8 9 10 11 12
股價 68 69 54 64 68 64 70 67 78 62 98 87
這個例子中, 聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那麼他最多能買4次股票。一種買法如下(可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
第1行: N (1 <= N <= 5000), 表示能買股票的天數。
第2行以下: N個正整數 (可能分多行) ，第i個正整數表示第i天的股價. 這些正整數大小不會超過longint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
只有一行，輸出兩個整數：
能夠買進股票的天數
長度達到這個值的股票購買方案數量
在計算解的數量的時候，如果兩個解所組成的字元串相同，那麼這樣的兩個解被認為是相同的（只能算做一個解）。因此，兩個不同的購買方案可能產生同一個字元串，這樣只能計算一次。
SAMPLE OUTPUT (file buylow.out)
4 2
參考程序如下：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct BIGNUM *bignum_t;
struct BIGNUM
{
int val;
bignum_t next;
};
int num[5000];
int len[5000];
int nlen;
bignum_t cnt[5000];
bignum_t get_big(void)
{
static bignum_t block;
static int size = 0;
if (size == 0)
{
block = (bignum_t)malloc(sizeof(*block)*128);
size = 128;
}
size--;
return block++;
}
/*初始化高精度數*/
void init_big(bignum_t *num, int val)
{
*num = get_big();
/* initialize */
(*num)->val = val;
(*num)->next = NULL;
}
void add(bignum_t a, bignum_t b)
{
int c; /* carry */
c = 0;
while (b || c)
{
a->val += c;
if (b) a->val += b->val;
/* if a->val is too large, we need to carry */
c = (a->val / 1000000);
a->val = (a->val % 1000000);
if (b) b = b->next;
if (!a->next && (b || c))
{ /* allocate if we need to */
a->next = get_big();
a = a->next;
a->val = 0;
a->next = NULL;
} else a = a->next;
}
}
void out_num(FILE *f, bignum_t v)
{
if (v->next)
{
out_num(f, v->next);
fprintf (f, "%06i", v->val);
}
else
fprintf (f, "%i", v->val);
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2;
int c;
int max;
int l;
bignum_t ans;
if ((fin = fopen("buylow.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("buylow.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &nlen);
for (lv = 0; lv < nlen; lv++)
fscanf (fin, "%d", &num[lv]);
/* 用DP計算最大長度*/
for (lv = 0; lv < nlen; lv++)
{
max = 1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (num[lv2] > num[lv] && len[lv2]+1 > max) max = len[lv2]+1;
len[lv] = max;
}
for (lv = 0; lv < nlen; lv++)
{
if (len[lv] == 1) init_big(&cnt[lv], 1);
else
{
init_big(&cnt[lv], 0);
l = -1;
max = len[lv]-1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (len[lv2] == max && num[lv2] > num[lv] && num[lv2] != l)
add(cnt[lv], cnt[lv2]);
l = num[lv2];
}
}
}
/* 找最長串*/
max = 0;
for (lv = 0; lv < nlen; lv++)
if (len[lv] > max) max = len[lv];
init_big(&ans, 0);
l = -1;
for (lv = nlen-1; lv >= 0; lv--)
if (len[lv] == max && num[lv] != l)
{
add(ans, cnt[lv]);
l = num[lv];
}
/* output answer */
fprintf (fout, "%i ", max);
out_num(fout, ans);
fprintf (fout, "\n");
return 0;
}
動態規劃作為一種重要的信息學競賽演算法，具有很強的靈活性。以上提供的是一些入門練習題，深入的學習還需要逐步積累經驗。

9. 詳解動態規劃演算法

其實你可以這么去想。
能用動態規劃解決的問題，肯定能用搜索解決。
但是搜素時間復雜度太高了，怎麼優化呢？
你想到了記憶化搜索，就是搜完某個解之後把它保存起來，下一次搜到這個地方的時候，調用上一次的搜索出來的結果。這樣就解決了處理重復狀態的問題。
動態規劃之所以速度快是因為解決了重復處理某個狀態的問題。
記憶化搜索是動態規劃的一種實現方法。
搜索到i狀態，首先確定要解決i首先要解決什麼狀態。
那麼那些狀態必然可以轉移給i狀態。
於是你就確定了狀態轉移方程。
然後你需要確定邊界條件。
將邊界條件賦予初值。
此時就可以從前往後枚舉狀態進行狀態轉移拉。