dynamic programming

 分治法和貪心法，它們都是将問題執行個體歸納為更小的、相似的子問題，并通過求解子問題産生一個全局最優解。

貪心法的目前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇和子問題。是以貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的 (即不包含公共的子子問題)，是以一旦遞歸地求出各子問題的解後，便可自下而上地将子問題的解合并成問題的解。

但不足的是，如果目前選擇可能要依賴子問題的解時，則難以通過局部的貪心政策達到全局最優解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題。

解決上述問題的辦法是利用動态規劃。該方法主要應用于最優化問題，找出其中最優(最大或最小)值的解。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動态規劃允許這些子問題不獨立，(亦即各子問題可包含公共的子子問題),對重複出現的子問題隻解一次，并将結果儲存起來，避免每次碰到時都要重複計算。該方法也允許其通過自身子問題的解作出選擇。

動态規劃是運籌學的一個分支，是求解決策過程最優化的數學方法。

20世紀50年代初美國數學家r.e.bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法——動态規劃。1957年出版了他的名著dynamic programming，這是該領域的第一本著作。

動态規劃問世以來，在經濟管理、生産排程、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源配置設定、裝置更新、排序、裝載等問題，用動态規劃方法比用其它方法求解更為友善。

一道取自網上的例題:

從鍵盤上輸入兩個自然數n和k（n<=100,k<=10），從1，2，。。。，n中任取k個數，要求所取的k個數中，任意兩個數不能相差1。程式設計求有多少種取法。

input

6 3

output

4

/*(1,3,5),(1,3,6),(1,4,6),(2,4,6)*/

[code]

<code>#include&lt;stdio.h&gt; int main() {     int n,k,i,j,a[100][100];     while(scanf("%d %d",&amp;n,&amp;k)!=eof)     {         for(i=1;i&lt;=n;i++)              a[i][1]=i;         for(i=2;i&lt;=k;i++)              a[1][i]=0;         for(i=2;i&lt;=n;i++)         {             for(j=2;j&lt;=k;j++)             {                 if(i&lt;=j)                      a[i][j]=0;                 else                       a[i][j]=a[i-2][j-1]+a[i-1][j];             }         }         printf("%d",a[n][k]);     }     return 0; }</code>

<code>[/code]</code>

<code>//分析</code>

<code>用 f(i,j)表示從1到i中任取j個數，任意兩個數不能相鄰：如果取i，則不能取i-1，必須從1到i-2中取j-1個數，即f(i-2,j-1).如果不取i，則隻能從1到i-1中取j個數，即f(i-1,j).故f(i,j)= f(i-2,j-1)+ f(i-1,j); f[i,1]=i; f[1,i]=0;   這個遞推式的結果是:矩形的上三角全0(a[1][1]元素除外),第一列為[1~n],其它元素為a[i-2][j-1]+a[i-1][j],最終所要的結果在a[n][k].(為什麼是這樣,自己多推幾步就知道了)</code>