目錄（點選跳轉）
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#i1">動态規劃求解的一般思路</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#i2">備忘錄法</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q1">1.硬币找零</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q2">2.字元串相似度/編輯距離（edit distance）</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q3">3.最長公共子序列(Longest Common Subsequence,lcs)</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q4">4.最長遞增子序列（Longest Increasing Subsequence,lis）</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q5">5.最大連續子序列和/積</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q6">6.矩陣鍊乘法</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q7">7.0-1背包問題</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q8">8.有代價的最短路徑</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q9">9.瓷磚覆寫（狀态壓縮DP）</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q10">10.工作量劃分</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q11">11.三路取蘋果</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#ref">參考資料</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#a1">附錄1：其他的一些動态規劃問題與解答（連結）</a>
<a href="http://www.cnblogs.com/wuyuegb2312/p/3281264.html#a2">附錄2：《算法設計手冊》第八章 動态規劃 面試題解答</a>
判斷問題的子結構（也可看作狀态），當具有最優子結構時，動态規劃可能适用。
求解重疊子問題。一個遞歸算法不斷地調用同一問題，遞歸可以轉化為查表進而利用子問題的解。分治法則不同，每次遞歸都産生新的問題。
重新構造一個最優解。
動态規劃的一種變形，使用自頂向下的政策，更像遞歸算法。
初始化時表中填入一個特殊值表示待填入，當遞歸算法第一次遇到一個子問題時，計算并填表；以後每次遇到時隻需傳回以前填入的值。
執行個體可以參照矩陣鍊乘法部分。
難度評級：
假設有幾種硬币，如1、3、5，并且數量無限。請找出能夠組成某個數目的找零所使用最少的硬币數。
解法：
用待找零的數值k描述子結構/狀态，記作sum[k]，其值為所需的最小硬币數。對于不同的硬币面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。對應于給定數目的找零total，需要求解sum[total]的值。
通過sum[total].lastSum和sum[total].addCoin，很容易通過循環逆序地或者編寫遞歸調用的函數正序地輸出從結束狀态到開始狀态使用的硬币種類。以下各題輸出狀态轉換的方法同樣，不再贅述。下面為了友善起見，有的題沒有在構造子結構的解時記錄狀态轉換，如果需要請類似地完成。
擴充：
分析：
這道題中，目前位置(i,j)是狀态，用M[i][j]來表示到達狀态(i,j)所能得到的最多蘋果數，那麼M[i][j] = max(M[i-1][j],M[i][j-1]) + A[i][j] 。特殊情況是M[1][1]=A[1][1]，當i=1且j!=1時,M[i][j] = M[i][j-1] + A[i][j]；當i!=1且j=1時M[i][j] = M[i-1][j] + A[i][j]。
求解程式略。
對于序列S和T，它們之間距離定義為：對二者其一進行幾次以下的操作(1)删去一個字元；(2)插入一個字元；(3)改變一個字元。每進行一次操作，計數增加1。将S和T變為同一個字元串的最小計數即為它們的距離。給出相應算法。
将S和T的長度分别記為len(S)和len(T)，并把S和T的距離記為m[len(S)][len(T)]，有以下幾種情況：
如果末尾字元相同，那麼m[len(S)][len(T)]=m[len(S)-1][len(T)-1]；
如果末尾字元不同，有以下處理方式
修改S或T末尾字元使其與另一個一緻來完成，m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1；
在S末尾插入T末尾的字元，比較S[1...len(S)]和S[1...len(T)-1]；
在T末尾插入S末尾的字元，比較S[1...len(S)-1]和S[1...len(T)]；
删除S末尾的字元，比較S[1...len(S)-1]和S[1...len(T)]；
删除T末尾的字元，比較S[1...len(S)]和S[1...len(T)-1]；
總結為，對于i>0,j>0的狀态(i,j),m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)。
這裡的重疊子結構是S[1...i]，T[1...j]。
以下是相應代碼。考慮到C語言數組下标從0開始，做了一個轉化将字元串後移一位。
字元串相似度/edit distance
應用：
難度評級：
修改兩處即可進行子串比對：
修改部分
如果j= strlen(S) - strlen(T)，那麼說明T是S的一個子串。
（這部分是根據《算法設計手冊》8.2.4和具體執行個體Skiena與Skienaa、Skiena與somta的分析獲得的，解釋不夠全面，可能有誤，請注意）
将match時不比對的代價轉化為最大長度即可：
match()
此時，最小值是兩者不同部分的距離。
（這部分同樣也不好了解，對于最長公共子序列，建議直接使用下一部分中的解法）
如果在編輯距離中各個操作的代價不同，如何尋找最小代價？
對于序列S和T，求它們的最長公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}則它們的lcs是{B,C,B,A}和{B,D,A,B}。求出一個即可。
和2類似，對于X[1...m]和Y[1...n]，它們的任意一個lcs是Z[1...k]。
(1)如果X[m]=Y[n]，那麼Z[k]=X[m]=Y[n],且Z[1...k-1]是X[1...m-1]和Y[1...n-1]的一個lcs；
(2)如果X[m]!=Y[n]，那麼Z[k]!=X[m]時Z是X[1...m-1]和Y的一個lcs；
(3)如果X[m]!=Y[n]，那麼Z[k]!=Y[n]時Z是X和Y[1...n-1]的一個lcs；
下面是《算法導論》上用僞碼描述的lcs算法。其中c[i][j]記錄目前lcs長度，b[i][j]記錄到達該狀态的上一個狀态。
如何輸出所有的LCS？
根據上面c[i,j]和b[i,j]的構造過程可以發現如果c[i-1,j]==c[i,j-1]，那麼分别向上和向左傳回的上一個狀态都是可行的。如果将其标記為“左/上”并通過遞歸調用來生成從c[m,n]到c[1,1]的所有路徑，就能找出所有的LCS。時間複雜度上界為O(mn)。
通過LCS獲得最長遞增自子序列。
對于1個序列，如243517698，最大值9，最小值1，那麼通過将它與123456789求LCS得到的就是最長連續遞增子序列23568。
這種做法不适用于最長連續非遞減子序列，除非能獲得重複最多的元素數目，如2433517698，那麼可以用112233445566778899與之比較。
使用專門的最長遞增子序列算法可以進行優化，詳見下一部分。
對于一個序列如1，-1，2，-3，4，-5，6，-7，其最長第增子序列為1,2,4,6。
除了利用3中lcs來求解，這裡使用求解lis問題的專門方法。
先看看如何确定子結構的表示。對于長度為k的序列s[1...k]，如果用lis[k]記錄這個序列中最長子序列似乎沒什麼用，因為在構造lis[k+1]時，需要比較s[k]與前面長度為lis[k]的lis的最後一個元素、s[1...k]中長度為lis[k]-1的序列的最後一個元素等等，沒有提供什麼便利，這個方案被否決。
為了将每個lis[k]轉化為構造lis[k+1]時有用的資料，把子結構記為以s[k]為結尾的lis的長度，那麼對于s[k+1]，需要檢查所有在它前面且小于它的元素s[i]，并令lis[k+1] = max(lis[i]+1),（i=1 to k,s[k+1]>s[i]）。這樣，一個O(n2)的算法便寫成了。為了在處理完成後不必再一次周遊lis[1...n]，可以使用一個MaxLength變量儲存目前記錄中最長的lis。
求解lis的加速
難度評級：
在構造lis[k+1]的時候可以發現，對于s[k+1]，真正有用的元素s[i]<s[k+1]且lis[i]最大。如果記錄了不同長度的lis的末尾元素，那麼對于新加入的元素s[k+1]，找出前面比它小的且對應lis最長的，就是以s[k+1]為結尾的lis[k+1]的長度。
可以發現使用數組MaxV[1...MAXLENGTH]其中MaxV[i]表示長度為i的lis的最小末尾元素，完全可以在s[k+1]時進行lis[k+1]的更新。進一步地發現，其實lis[]數組已經沒有用了，對于MaxV[1...MAXLENGTH]中值合法對應的最大下标，就是目前最長的lis，也即利用MaxV[]更新自身。
同時，根據MaxV[]的更新過程，可以得出當i<j時，MaxV[i]<MaxV[j]（假設出現了i>j且Max[i]=>Max[j]的情況，那麼在之前的進行中，在發現j長度的lis時，應用它的第i個元素來更新Max[i]，仍會導緻MaxV[i]<MaxV[j]，這與這個現狀發生了沖突，也即這個情況是不可能到達的）。這樣，在尋找小于s[k+1]的值時，可以使用二分查找，進而把時間複雜度降低至O(nlogn)。
在這個解法下，不妨考慮如何重構這個lis。
輸入是具有n個數的向量x，輸出時輸入向量的任何連續子向量的最大和。
這裡隻把O(n)的動态規劃解法列在下面，其中隻用一個變量儲存過去的狀态：
給定一個正浮點數數組，求它的一個最大連續子序列乘積的值。
對數組中每個元素取對數，構成新的數列，在新的數列上使用求最大連續子序列的算法。
如果求對數開銷較大，建議使用擴充2的方法。
給定一個浮點數數組，其值可正可負可零，求它的一個最大連續子序列乘積的值。（假定計算過程中，任意一個序列的積都不超過浮點數最大表示）
在最大連續子序列和算法的基礎上進行修改。由于負負得正，對于目前狀态array[k]，需要同時計算出它的最大值和最小值。即：
new_maxendinghere = max3(maxendinghere*array[k],minendinghere*array[k],array[k])
new_minendinghere = min3(maxendinghere*array[k],minendinghere*array[k],array[k])
此後對已周遊部分的最大積進行更新：
maxsofar = max(maxsofar,new_maxendinghere)
一個給定的矩陣序列A1A2...An計算連乘乘積，有不同的結合方法，并且在結合時，矩陣的相對位置不能改變，隻能相鄰結合。根據矩陣乘法的公式，10*100和100*5的矩陣相乘需要做10*100*5次标量乘法。那麼對于維數分别為10*100、100*5、5*50的矩陣A、B、C，用(A*B)*C來計算需要10*100*5 + 10*5*500 =7500次标量乘法；而A*(B*C)則需要100*5*50+10*100*50=75000次标量乘法。
那麼對于由n個矩陣構成的鍊<A1,A2,...,An>，對i-1,2,...n，矩陣Ai的維數為pi-1*pi，對乘積A1A2...An求出最小化标量乘法的加括号方案。
盡管可以通過遞歸計算取1<=k<n使得P(n)=∑P(k)P(n-k)，周遊所有P(n)種方案，但這并不是一個高效率的解法。
經過以上幾道題的鍛煉，很容易看出，子結構是求Ai...Aj的加括号方法m[i][j]可遞歸地定義為
這樣，隻需利用子結構求解m[1][n]即可，并在在構造m[1][n]的同時，記錄狀态轉換。下面的代碼展示了這個過程，不再仔細分析。
矩陣鍊乘法
矩陣鍊乘法的備忘錄解法（僞碼），來自《算法導論》第15章。
一個賊在偷竊一家商店時發現了n件物品，其中第i件值vi元，重wi磅。他希望偷走的東西總和越值錢越好，但是他的背包隻能放下W磅。請求解如何放能偷走最大價值的物品，這裡vi、wi、W都是整數。
如果每個物品都允許切割并隻帶走其一部分，則演變為部分背包問題，可以用貪心法求解。0-1背包問題經常作為貪心法不可解決的執行個體（可通過舉反例來了解），但可以通過動态規劃求解。
為了找出子結構的形式，粗略地分析發現，對前k件物品形成最優解時，需要決策第k+1件是否要裝入背包。但是此時剩餘容量未知，不能做出決策。是以把剩餘容量也考慮進來，形成的狀态由已決策的物品數目和剩餘容量兩者構成。這樣，所有狀态可以放入一個n*(W+1)的矩陣c中，其值為目前包中物品總價值，這時有
根據這個遞推公式，很容易寫出求解代碼。
0-1背包問題示例代碼
無向圖G中有N個頂點，并通過一些邊相連接配接，邊的權值均為正數。初始時你身上有M元，當走過i點時，需要支付S(i)元，如果支付不起表示不能通過。請找出頂點1到頂點N的最短路徑。如果不存在則傳回一個特殊值，如果存在多條則傳回最廉價的一條。限制條件：1<N<=100; 0<=M<=100 ; 對任意i, 0<=S[i]<=100。
如果不考慮經過頂點時的花費，這就簡化成了一個一般的兩點間最短路徑問題，可以用Dijkstra算法求解。加入了花費限制之後，就不能直接求解了。
考察從頂點0到達頂點i的不同狀态，會發現它們之間的差別是：總花費相同但路徑長度不同、總花費不同但路徑長度不同。為了尋找最短路徑，必然要儲存到達i點的最短路徑；同時為了找到最小開銷，應該把到達i點的開銷也進行儲存。根據題目的數值限制，可以将總開銷作為到達頂點i的一個狀态區分。這樣，就可以把Min[i][j]表示為到達頂點i（并經過付錢）時還剩餘j元錢的最短路徑的長度。在此基礎上修改Dijkstra算法，使其能夠儲存到達同一點不同花費時的最短長度，最終的Min[N-1][0...M]中最小的即為所求。以下是求解過程的僞代碼。
用 1 * 2 的瓷磚覆寫 n * m 的地闆，問共有多少種覆寫方式？
解法：
分析子結構，按行鋪瓷磚。一塊1*2瓷磚，橫着放對下一行的狀态沒有影響；豎着放時，下一行的對應一格就會被占用。是以，考慮第i行的鋪法時隻需考慮由第i-1行造成的條件限制。枚舉枚舉第i-1行狀态即可獲得i行可能的狀态，這裡為了與連結一文一緻，第i-1行的某格隻有兩個狀态：空或者放置。空表示第i行對應位置需要放置一個豎着的瓷磚，這時在鋪第i行時，除去限制以外，隻需考慮放還是不放橫着的瓷磚這2種情況即可（不必分為放還是不放、橫到下一層還是豎着一共4種）。同時對于第i-1行的放法，用二進制中0和1表示有無瓷磚，那麼按位取反恰好就是第i行的限制條件。
假設書架上一共有9本書，每本書各有一定的頁數，配置設定3個人來進行閱讀。為了便于管理，配置設定時，各書要求保持連續，比如第1、2、3本書配置設定給第1人，4、5配置設定給第二人，6，7，8，9配置設定給第3人，但不能1，4，2配置設定給第1人，3，5，6配置設定給第2人。即用兩個隔闆插入8個空隙中将9本書分成3部分，書不能換位。同時，配置設定時必須整本配置設定，同一本書不能拆成兩部分分給兩個人。為了公平起見，需要将工作量最大的那一部分最小化，請設計配置設定方案。用s1,...,sn表示各本書的頁數。
繼續從子結構的角度出發，發現如果前面的k-1份已經分好了，那麼第k份自然也就分好了。用M[n][k]表示将n本書分成k份時最小化的k份中的最大工作量，從第k份也就是最後一份的角度來看，總數-它的不同情況下數量 = 前k-1份的數量和。
除此以外，初始化為
自底向上地可以求得使M[n][k]最小化的解。
工作量劃分
其他：
這個問題被稱為線性分割(linear partition)問題，有不少的應用情形。如，一系列任務配置設定給幾個并行程序，那麼配置設定工作量最大任務的那個程序将成為影響最終完成時間的瓶頸。将最大的工作量盡量減少，能夠使所有工作更快地完成。
（問題1的相關問題(1)的進一步擴充）一個矩形區域被劃分為N*M個小矩形格子，在格子(i,j)中有A[i][j]個蘋果。現在從左上角的格子(1,1)出發，要求每次隻能向右走一步或向下走一步，每經過一個格子就把其中的蘋果全部拿走，最後到達(N,M)。此時，隻允許向上或向左走一步，反方向走回(1,1)。這一趟可以不走第一趟的路線，但當經過第一趟所經過的格子時，裡面已經沒有蘋果了。到達(1,1)後，再次反方向地隻允許向右或向下走，走到(N,M)，同樣可以不走前兩趟走過的路線。求這三趟的走法，使得最終能拿取最多數量的蘋果。
這個問題有兩個難點，首先要理清三條路線的關系。可以發現，雖然第二趟方向相反，但其實和從(1,1)走到(N,M)是一樣的，即三趟路線全部可以轉化為從(1,1)向下或向右走到(N,M)的過程。
觀察三條路線可以發現，實際中走的時候如果路線有交叉，可以把這種情況轉化為相遇而不交錯的情況如下圖：
這樣做的好處是，對于紅線和藍線上同一行j的點的坐标(i,j)(i',j)，總有i<=i',這樣就能夠把三條路線劃分成左、中、右三條有序的路線。
經過兩次轉化，可以構造子結構了。用Max[y-1][i][j][k]表示在y-1行時，三條路線分别在i、j、k時所能取得的最大蘋果數，用Max[y-1][i][j][k]可以求解任意的Max[y][i'][j'][k']，其中i' = i to j' , j' = j to k', k' = k to M. 如果線路重疊，蘋果已經被取走，不用重複考慮。是以處理每一行時為了簡單起見最好維護一個該位置蘋果是否被取走的标志位，友善在路線重疊時計算。根據上面的範圍關系，先求k'的所有情況，然後是j'，最後才是i'。這樣Max[N][M][M][M]就是三趟後所能取得的最多蘋果數。
《算法導論》第15章動态規劃、第16章貪心算法
《算法設計手冊》第八章動态規劃
《程式設計珠玑》相關問題
《程式設計之美》相關問題
<a href="http://blog.csdn.net/limchiang/article/details/8619611">poj 2411 & 程式設計之美 4.2 瓷磚覆寫地闆</a>
<a href="http://blog.csdn.net/wzy_1988/article/details/9319897">最大連續子序列乘積</a>
<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg" target="_blank">Dynamic Programming: From novice to advanced</a>
<a href="http://www.cppblog.com/doer-xee/archive/2009/11/30/102296.html" target="_blank">雙調歐幾裡德旅行商問題（算法導論思考題15-1）</a>
評：網絡上的很多中文版本，都不如直接看這篇文章裡的英文原版解答了解的清楚。
<a href="http://blog.csdn.net/wenlei_zhouwl/article/details/5992367" target="_blank">整齊列印（算法導論思考題15-4）</a>
評：難度不高，注意要求的是空格數的立方和最小。
<a href="http://zh.wikipedia.org/zh/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95" target="_blank">動态規劃應用：Viterbi算法</a>
評：需要一些馬爾科夫鍊的知識。了解起來不是很容易，了解以後是不是有種像是更多個生産線的裝備線排程？
<a href="http://www.cnblogs.com/longdouhzt/archive/2011/07/27/2117978.html" target="_blank">最高效益的排程（算法導論思考題15-7）</a>
評：和0-1背包問題何其相似。
8-24.
給定一個硬币種類的集合，找出湊出給定一個值所用的最小硬币數目。
解答：
正文問題1已做解答，略。
8-25.
長度為n的數組，其中元素可正可負可零。找出數組索引i,j使得從i到j的元素之和最大。
最大連續自序列和問題，請參考正文問題5的解答。
8-26.
假設你有一頁紙，正面和背面都寫滿了字母，當剪掉正面上一個字母時，這一頁的背面的字母也會被剪掉。設計一個算法來驗證是否能通過這張紙生成一個給定的字元串？提供一個函數，當你輸入一個字母的位置時能夠傳回它背面的字母。（叙述關鍵思路即可）
下面把思路大意翻譯一下。
假設需要拼成的字元串是"FOO"，同時這張紙的正反面對應位置上的内容（可以通過提供的函數獲得）分别是：
位置
1
2
3
4
正面
F
C
O
Z
反面
K
由于位置4上的字母的正反面都用不到，忽略。
把這個表格轉化成一個兩層結點的流量網絡
其中源點下面第一層表示拼成所需字元串的所有字母，源點到達該點的流量是需要的數目。第一層與第二層相連接配接表示某一位置上對應的是哪個所需字母，比如位置1正反面分别是F和O，表示它能提供1個F的入度和1個O的入度，但又由于一個片紙無論正反面隻能用一次，那麼它隻能提供1的出度，直接連接配接彙點。
這個問題是否有解，等價于這個流量網絡中是否存在一個流使得源點的流的出度等于彙點流的的入度，即一個最大流問題。
本文轉自五嶽部落格園部落格，原文連結：www.cnblogs.com/wuyuegb2312/p/3281264.html，如需轉載請自行聯系原作者