原文：http://blog.csdn.net/u013445530/article/details/45645307#

什么是動態(tài)規(guī)劃 ?

動態(tài)規(guī)劃( D ynamic P rogramming ，所以我們簡稱動態(tài)規(guī)劃為 DP )是 運(yùn)籌學(xué) 的一個分支，是求解決策過程(decision process) 最優(yōu)化的數(shù)學(xué)方法。 20 世紀(jì) 50 年代初 美國 數(shù)學(xué)家R.E.Bellman 等人在研究多階段決策過程 (multistep decision process) 的優(yōu)化問題時，提出了著名的最優(yōu)化原理 (principle of optimality) ，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法 —— 動態(tài)規(guī)劃。 1957 年出版了他的名著《 Dynamic Programming 》，這是該領(lǐng)域的第一本著作。
動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)。當(dāng)前子問題的解將由上一次子問題的解推出。使用動態(tài)規(guī)劃來解題只需要多項式時間復(fù)雜度，因此它比回溯法、暴力法等要快許多。
說了這么多術(shù)語，想必大家都很頭疼， 現(xiàn)在讓我們通過一個例子來了解一下DP 的基本原理。

首先，我們要找到某個狀態(tài)的最優(yōu)解，然后在它的幫助下，找到下一個狀態(tài)的最優(yōu)解。?

這句話暫時理解不了沒關(guān)系，請看下面的例子 :

硬幣問題：

如果我們有面值為1 元、 3 元和 5 元的硬幣若干枚，如何用最少的硬幣湊夠 11 元？我們憑直觀感覺告訴自己，先選面值最大，因此最多選 2枚 5 元的硬幣，現(xiàn)在是 10 元了，還差一元，接下來我們挑選第二大的 3 元硬幣，發(fā)現(xiàn)不行（ 10+3=13 超了），因此我們繼續(xù)選第三大的硬幣也就是 1 元硬幣，選一個就可以（ 10+1=11 ），所以總共用了 3 枚硬幣湊夠了 11 元。這就是貪心法，每次選最大的。但是我們將面值改為 2 元， 3 元和 5 元的硬幣，再用貪心法就不行了。為什么呢？按照貪心思路，我們同樣先取 2 枚最大 5 元硬幣，現(xiàn)在 10 元了，還差一元，接下來選第二大的，發(fā)現(xiàn)不行，再選第三大的，還是不行，這時用貪心方法永遠(yuǎn)湊不出 11 元，但是你仔細(xì)看看，其實我們可以湊出 11 元的， 2 枚 3 元硬幣和 1 枚五元硬幣就行了，這是人經(jīng)過思考判斷出來了的，但是怎么讓計算機(jī)算出來呢？

這就要用動態(tài)規(guī)劃的思想：

首先我們思考一個問題，如何用最少的硬幣湊夠i 元 (i<11) ？為什么要這么問呢？兩個原因： 1. 當(dāng)我們遇到一個大問題時，總是習(xí)慣把問題的規(guī)模變小，這樣便于分析討論。 2. 這個規(guī)模變小后的問題和原來的問題是同質(zhì)的，除了規(guī)模變小，其它的都是一樣的，本質(zhì)上它還是同一個問題 ( 規(guī)模變小后的問題其實是原問題的子問題 ) 。
好了，讓我們從最小的i 開始吧。當(dāng) i=0 ，即我們需要多少個硬幣來湊夠 0 元。由于 1 ， 3 ， 5 都大于 0 ，即沒有比 0 小的幣值，因此湊夠 0 元我們最少需要 0 個硬幣。 ( 這個分析很傻是不是？別著急，這個思路有利于我們理清動態(tài)規(guī)劃究竟在做些什么。 ) 這時候我們發(fā)現(xiàn)用一個標(biāo)記來表示這句 “ 湊夠 0 元我們最少需要 0 個硬幣。 ” 會比較方便，如果一直用純文字來表述，不出一會兒你就會覺得很繞了。那么，我們用 d(i)=j 來表示湊夠 i 元最少需要 j 個硬幣。于是我們已經(jīng)得到了 d(0)=0 ，表示湊夠 0 元最小需要 0 個硬幣。當(dāng) i=1 時，只有面值為 1 元的硬幣可用，因此我們拿起一個面值為 1 的硬幣，接下來只需要湊夠 0 元即可，而這個是已經(jīng)知道答案的，即 d(0)=0 。所以， d(1)=d(1-1)+1=d(0)+1=0+1=1 。當(dāng) i=2 時，仍然只有面值為 1 的硬幣可用，于是我拿起一個面值為 1 的硬幣，接下來我只需要再湊夠 2-1=1 元即可 ( 記得要用最小的硬幣數(shù)量 ) ，而這個答案也已經(jīng)知道了。所以 d(2)=d(2-1)+1=d(1)+1=1+1=2 。一直到這里，你都可能會覺得，好無聊，感覺像做小學(xué)生的題目似的。因為我們一直都只能操作面值為 1 的硬幣！耐心點，讓我們看看 i=3 時的情況。當(dāng) i=3 時，我們能用的硬幣就有兩種了： 1 元的和 3 元的 ( 5 元的仍然沒用，因為你需要湊的數(shù)目是 3 元！ 5 元太多了親 ) 。既然能用的硬幣有兩種，我就有兩種方案。如果我拿了一個 1 元的硬幣，我的目標(biāo)就變?yōu)榱?#xff1a;湊夠 3-1=2 元需要的最少硬幣數(shù)量。即 d(3)=d(3-1)+1=d(2)+1=2+1=3 。這個方案說的是，我拿 3 個 1 元的硬幣；第二種方案是我拿起一個 3 元的硬幣，我的目標(biāo)就變成：湊夠 3-3=0 元需要的最少硬幣數(shù)量。即 d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個方案說的是，我拿 1 個 3 元的硬幣。好了，這兩種方案哪種更優(yōu)呢？記得我們可是要用最少的硬幣數(shù)量來湊夠 3 元的。所以，選擇 d(3)=1 ，怎么來的呢？具體是這樣得到的： d(3)=min{d(3-1)+1, d(3-3)+1} 。
OK，碼了這么多字講具體的東西，讓我們來點抽象的。從以上的文字中，我們要抽出動態(tài)規(guī)劃里非常重要的兩個概念：狀態(tài)和狀態(tài)轉(zhuǎn)移方程。
上文中d(i) 表示湊夠 i 元需要的最少硬幣數(shù)量，我們將它定義為該問題的 " 狀態(tài) " ，這個狀態(tài)是怎么找出來的呢？根據(jù)子問題定義狀態(tài)。你找到子問題，狀態(tài)也就浮出水面了。最終我們要求解的問題，可以用這個狀態(tài)來表示： d(11) ，即湊夠 11 元最少需要多少個硬幣。那狀態(tài)轉(zhuǎn)移方程是什么呢？既然我們用 d(i) 表示狀態(tài)，那么狀態(tài)轉(zhuǎn)移方程自然包含 d(i) ，上文中包含狀態(tài) d(i) 的方程是： d(3)=min{d(3-1)+1, d(3-3)+1} 。沒錯，它就是狀態(tài)轉(zhuǎn)移方程，描述狀態(tài)之間是如何轉(zhuǎn)移的。當(dāng)然，我們要對它抽象一下，
d(i)=min{ d(i-v j )+1 }，其中 i-v j >=0， v j 表示第j 個硬幣的面值 ;

有了狀態(tài)和狀態(tài)轉(zhuǎn)移方程，這個問題基本上也就解決了。當(dāng)然了，Talk is cheap,show me the code!

int main() {int a[3] = {1,3,5},sum = 11,cent = 0,dp[12];dp[0] = 0;for(int i = 1; i <= sum; i++) dp[i] = i;//我們假設(shè)存在1元的硬幣那么i元最多只需要i枚1元硬幣，當(dāng)然最好設(shè)置dp[i]等于無窮大for(int i = 1; i <= sum; i++){for(int j = 0; j < 3; j++){if(i >= a[j] && dp[i - a[j]] + 1 < dp[i]){dp[i] = dp[i- a[j] ] + 1;}}}cout<<dp[sum]<<endl;return 0; }從上圖可以得出，要湊夠11元至少需要3枚硬幣。
此外，通過追蹤我們是如何從前一個狀態(tài)值得到當(dāng)前狀態(tài)值的，可以找到每一次我們用的是什么面值的硬幣。比如，從上面的圖我們可以看出，最終結(jié)果d(11)=d(10)+1(面值為1)，而d(10)=d(5)+1(面值為5)，最后d(5)=d(0)+1 (面值為5)。所以我們湊夠11元最少需要的3枚硬幣是：1元、5元、5元。

通過硬幣問題我們初識DP的原理，其實可以說貪心問題是DP問題的特例，現(xiàn)在我們通過幾道題目加深對DP問題的理解

數(shù)塔問題：

數(shù)塔問題是動態(tài)規(guī)劃經(jīng)典的題目，下面來初步講解下
將一個由N行數(shù)字組成的三角形，如圖所以，設(shè)計一個算法，計算出三角形的由頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。
學(xué)弟學(xué)妹們你們之前學(xué)過DFS和BFS，第一眼看過去這題應(yīng)該用DFS解決，沒錯，DFS也可以，但是我們觀察下n行總共有(1 + 2 + 3 + 4+...+n) = （1+n）*n/2個節(jié)點，在遞歸求解的過程中很多節(jié)點被重復(fù)訪問了，這就導(dǎo)致時間大大增加，必然超時

但是如果用DP的話這個節(jié)點可以只訪問一次

好了，現(xiàn)在我們用DP解決這道問題

將上圖轉(zhuǎn)化一下：

假設(shè)上圖用map[][]數(shù)組保存。
令f[i][j]表示從頂點(1, 1)到頂點(i, j)的最大值。
則可以得到狀態(tài)轉(zhuǎn)移方程：
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
此題既適合自頂而下的方法做，也適合自底而上的方法，
當(dāng)用自頂而下的方法做時，最后要在在最后一列數(shù)中找出最大值，
而用自底而上的方法做時，f[1][1]即為最大值。
所以我們將圖2根據(jù)狀態(tài)轉(zhuǎn)移方程可以得到圖3：

最大值是30.
代碼如下:

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int a[2000][2000]; int main() { int t,n,i,j; while(~scanf("%d",&n)) { for(i=0; i<n; i++) for(j=0; j<=i; j++) scanf("%d",&a[i][j]); for(i=n-1; i>0; i--) for(j=0; j<i; j++) a[i-1][j]+=max(a[i][j],a[i][j+1]); printf("%d\n",a[0][0]); } return 0; } 上面討論了兩個非常簡單的例子。現(xiàn)在讓我們來看看對于更復(fù)雜的問題， 如何找到狀態(tài)之間的轉(zhuǎn)移方式(即找到狀態(tài)轉(zhuǎn)移方程)。為此我們要引入一個新詞叫遞推關(guān)系來將狀態(tài)聯(lián)系起來(說的還是狀態(tài)轉(zhuǎn)移方程)
OK，上例子，看看它是如何工作的。

最長非降子序列：
一個序列有N個數(shù)：A[1],A[2],…,A[N]，求出最長非降子序列的長度。 (講DP基本都會講到的一個問題LIS：longest increasing subsequence)
正如上面我們講的，面對這樣一個問題，我們首先要定義一個“狀態(tài)”來代表它的子問題，并且找到它的解。注意，大部分情況下，某個狀態(tài)只與它前面出現(xiàn)的狀態(tài)有關(guān)，而獨(dú)立于后面的狀態(tài)。
讓我們沿用“入門”一節(jié)里那道簡單題的思路來一步步找到“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”。 假如我們考慮求A[1],A[2],…,A[i]的最長非降子序列的長度，其中i<N，那么上面的問題變成了原問題的一個子問題(問題規(guī)模變小了，你可以讓i=1,2,3等來分析) 然后我們定義d(i)，表示前i個數(shù)中以A[i]結(jié)尾的最長非降子序列的長度。OK，對照“入門”中的簡單題，你應(yīng)該可以估計到這個d(i)就是我們要找的狀態(tài)。如果我們把d(1)到d(N)都計算出來，那么最終我們要找的答案就是這里面最大的那個。狀態(tài)找到了，下一步找出狀態(tài)轉(zhuǎn)移方程。
為了方便理解我們是如何找到狀態(tài)轉(zhuǎn)移方程的，我先把下面的例子提到前面來講。如果我們要求的這N個數(shù)的序列是：
5，3，4，8，6，7
根據(jù)上面找到的狀態(tài)，我們可以得到：（下文的最長非降子序列都用LIS表示）
· 前1個數(shù)的LIS長度d(1)=1(序列：5)
· 前2個數(shù)的LIS長度d(2)=1(序列：3；3前面沒有比3小的)
· 前3個數(shù)的LIS長度d(3)=2(序列：3，4；4前面有個比它小的3，所以d(3)=d(2)+1)
· 前4個數(shù)的LIS長度d(4)=3(序列：3，4，8；8前面比它小的有3個數(shù)，所以 d(4)=max{d(1),d(2),d(3)}+1=3)
OK，分析到這，我覺得狀態(tài)轉(zhuǎn)移方程已經(jīng)很明顯了，如果我們已經(jīng)求出了d(1)到d(i-1)，那么d(i)可以用下面的狀態(tài)轉(zhuǎn)移方程得到：
d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
用大白話解釋就是，想要求d(i)，就把i前面的各個子序列中，最后一個數(shù)不大于A[i]的序列長度加1，然后取出最大的長度即為d(i)。當(dāng)然了，有可能i前面的各個子序列中最后一個數(shù)都大于A[i]，那么d(i)=1，即它自身成為一個長度為1的子序列。
分析完了，上圖：(第二列表示前i個數(shù)中LIS的長度，第三列表示，LIS中到達(dá)當(dāng)前這個數(shù)的上一個數(shù)的下標(biāo)，根據(jù)這個可以求出LIS序列)

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> usingnamespace std; int main() { int dp[2000],a[2000],n; while(cin>>n) { memset(dp,0,sizeof(dp)); intres = 0; for(inti = 0; i < n; i++) cin>>a[i]; . for(inti = 0; i < n; i++) { dp[i] = 1; for(intj = 0; j < i; j++) { if(a[j] < a[i]) dp[i] = max(dp[i],dp[j] + 1); } res = max(res,dp[i]); } cout<<res<<endl; } return0; }

總結(jié)：

1，縮小規(guī)模，子問題本質(zhì)上還是原問題

2，找狀態(tài)和狀態(tài)轉(zhuǎn)移方程

總結(jié)

以上是生活随笔為你收集整理的动态规划思想的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。