教程基本框架和部分內容轉自Hawstein
出處：http://hawstein.com/posts/dp-novice-to-advanced.html
聲明：本文采用以下協(xié)議進行授權：自由轉載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0帽蝶，轉載請注明作者及出處躺酒。
本文翻譯自TopCoder上的一篇文章：Dynamic Programming: From novice to advanced
（原創(chuàng)部分）補充聲明：代碼為作者原創(chuàng)戈次，自由轉載-非商用。
keyword: Dynamic Planning, 背包問題伞芹，longest increasing subsequence, binary search optimisation of LIS problem,
簡介(入門)
什么是動態(tài)規(guī)劃，我們要如何描述它?
動態(tài)規(guī)劃算法通常基于一個遞推公式及一個或多個初始狀態(tài)唱较。 當前子問題的解將由上一次子問題的解推出扎唾。使用動態(tài)規(guī)劃來解題只需要多項式時間復雜度， 因此它比回溯法南缓、暴力法等要快許多胸遇。
現(xiàn)在讓我們通過一個例子來了解一下DP的基本原理。
首先汉形，我們要找到某個狀態(tài)的最優(yōu)解纸镊，然后在它的幫助下，找到下一個狀態(tài)的最優(yōu)解概疆。
“狀態(tài)”代表什么及如何找到它?
“狀態(tài)”用來描述該問題的子問題的解逗威。
如果我們有面值為1元、3元和5元的硬幣若干枚岔冀，如何用最少的硬幣湊夠11元凯旭？ (表面上這道題可以用貪心算法，但貪心算法無法保證可以求出解楣颠，比如1元換成2元的時候)
首先我們思考一個問題尽纽，如何用最少的硬幣湊夠i元(i<11)？為什么要這么問呢童漩？
兩個原因：
1.當我們遇到一個大問題時弄贿，總是習慣把問題的規(guī)模變小，這樣便于分析討論矫膨。
2.這個規(guī)模變小后的問題和原來的問題是同質的差凹，除了規(guī)模變小，其它的都是一樣的侧馅， 本質上它還是同一個問題(規(guī)模變小后的問題其實是原問題的子問題)危尿。
好了，讓我們從最小的i開始吧馁痴。當i=0谊娇，即我們需要多少個硬幣來湊夠0元。
由于1罗晕，3济欢，5都大于0，即沒有比0小的幣值小渊，因此湊夠0元我們最少需要0個硬幣法褥。 (這個分析很傻是不是？別著急酬屉，這個思路有利于我們理清動態(tài)規(guī)劃究竟在做些什么半等。)
這時候我們發(fā)現(xiàn)用一個標記來表示這句“湊夠0元我們最少需要0個硬幣揍愁。”會比較方便杀饵， 如果一直用純文字來表述莽囤，不出一會兒你就會覺得很繞了。
那么切距， 我們用d(i)=j來表示湊夠i元最少需要j個硬幣烁登。于是我們已經(jīng)得到了d(0)=0， 表示湊夠0元最小需要0個硬幣蔚舀。
當i=1時饵沧，只有面值為1元的硬幣可用， 因此我們拿起一個面值為1的硬幣赌躺，接下來只需要湊夠0元即可狼牺，而這個是已經(jīng)知道答案的， 即d(0)=0礼患。
所以是钥，d(1)=d(1-1)+1=d(0)+1=0+1=1。
當i=2時缅叠， 仍然只有面值為1的硬幣可用悄泥，于是我拿起一個面值為1的硬幣， 接下來我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數(shù)量)肤粱，而這個答案也已經(jīng)知道了弹囚。
所以d(2)=d(2-1)+1=d(1)+1=1+1=2。
一直到這里领曼，你都可能會覺得鸥鹉，好無聊， 感覺像做小學生的題目似的庶骄。因為我們一直都只能操作面值為1的硬幣毁渗！耐心點， 讓我們看看i=3時的情況单刁。
當i=3時灸异，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用，因為你需要湊的數(shù)目是3元羔飞！5元太多了親)肺樟。 既然能用的硬幣有兩種，我就有兩種方案褥傍。如果我拿了一個1元的硬幣儡嘶，
我的目標就變?yōu)榱耍?湊夠3-1=2元需要的最少硬幣數(shù)量喇聊。
即d(3)=d(3-1)+1=d(2)+1=2+1=3恍风。 這個方案說的是，我拿3個1元的硬幣；第二種方案是我拿起一個3元的硬幣朋贬， 我的目標就變成：湊夠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)轉移方程滞项。
上文中d(i)表示湊夠i元需要的最少硬幣數(shù)量狭归，我們將它定義為該問題的”狀態(tài)”， 這個狀態(tài)是怎么找出來的呢文判？我在另一篇文章 動態(tài)規(guī)劃之背包問題(一)中寫過： 根據(jù)子問題定義狀態(tài)过椎。你找到子問題，狀態(tài)也就浮出水面了戏仓。 最終我們要求解的問題潭流，可以用這個狀態(tài)來表示：d(11)，即湊夠11元最少需要多少個硬幣柜去。 那狀態(tài)轉移方程是什么呢灰嫉？
既然我們用d(i)表示狀態(tài)，那么狀態(tài)轉移方程自然包含d(i)嗓奢， 上文中包含狀態(tài)d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}讼撒。
沒錯， 它就是狀態(tài)轉移方程股耽，描述狀態(tài)之間是如何轉移的根盒。當然，我們要對它抽象一下物蝙，
d(i)=min{ d(i-vj)+1 }炎滞，其中i-vj >=0，vj表示第j個硬幣的面值;
有了狀態(tài)和狀態(tài)轉移方程诬乞，這個問題基本上也就解決了册赛。當然了钠导，Talk is cheap,show me the code!
Hawstein 的偽代碼如下：
我的python實現(xiàn)在此：
這個方法沒有用循環(huán)來簡化書寫，可能對萌新來說好理解一點森瘪，可以參考一下牡属。
下圖是當i從0到11時的解：
從上圖可以得出，要湊夠11元至少需要3枚硬幣扼睬。
此外逮栅，通過追蹤我們是如何從前一個狀態(tài)值得到當前狀態(tài)值的， 可以找到每一次我們用的是什么面值的硬幣窗宇。比如措伐，從上面的圖我們可以看出， 最終結果d(11)=d(10)+1(面值為1)军俊，而d(10)=d(5)+1(面值為5)废士，最后d(5)=d(0)+1 (面值為5)。所以我們湊夠11元最少需要的3枚硬幣是：1元蝇完、5元官硝、5元。
初級
注：我一開始都看暈了短蜕，子序列就是subsequence氢架。
在數(shù)學中，某個序列的子序列是從最初序列通過去除某些元素但不破壞余下元素的相對位置（在前或在后）而形成的新序列 ----Wikipedia
上面討論了一個非常簡單的例子∨竽В現(xiàn)在讓我們來看看對于更復雜的問題岖研， 如何找到狀態(tài)轉移方程。 為此我們要引入一個新詞叫遞推關系來將狀態(tài)聯(lián)系起來(說的還是狀態(tài)轉移方程)
OK警检，上例子孙援，看看它是如何工作的。
一個序列有N個數(shù)：A[1],A[2],…,A[N]扇雕，求出最長非降子序列的長度拓售。 (講DP基本都會講到的一個問題LIS：longest increasing subsequence)
正如上面我們講的，面對這樣一個問題镶奉，我們首先要定義一個“狀態(tài)”來代表它的子問題础淤， 并且找到它的解。注意哨苛，大部分情況下鸽凶，某個狀態(tài)只與它前面出現(xiàn)的狀態(tài)有關， 而獨立于后面的狀態(tài)建峭。
讓我們沿用“入門”一節(jié)里那道簡單題的思路來一步步找到“狀態(tài)”和“狀態(tài)轉移方程”玻侥。 假如我們考慮求A[1],A[2],…,A[i]的最長非降子序列的長度，其中i<N亿蒸， 那么上面的問題變成了原問題的一個子問題(問題規(guī)模變小了凑兰，你可以讓i=1,2,3等來分析) 然后我們定義d(i)掌桩，表示前i個數(shù)中以A[i]結尾的最長非降子序列的長度。OK票摇， 對照“入門”中的簡單題，你應該可以估計到這個d(i)就是我們要找的狀態(tài)砚蓬。 如果我們把d(1)到d(N)都計算出來矢门，那么最終我們要找的答案就是這里面最大的那個。 狀態(tài)找到了灰蛙，下一步找出狀態(tài)轉移方程祟剔。
為了方便理解我們是如何找到狀態(tài)轉移方程的，我先把下面的例子提到前面來講摩梧。 如果我們要求的這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)轉移方程已經(jīng)很明顯了，如果我們已經(jīng)求出了d(1)到d(i-1)滨砍， 那么d(i)可以用下面的狀態(tài)轉移方程得到：
d(i) = max{1, d(j)+1}, 其中j<i,A[j]<=A[i]
用大白話解釋就是拉馋，想要求d(i)，就把i前面的各個子序列中惨好， 最后一個數(shù)不大于A[i]的序列長度加1煌茴，然后取出最大的長度即為d(i)。 當然了日川，有可能i前面的各個子序列中最后一個數(shù)都大于A[i]蔓腐，那么d(i)=1， 即它自身成為一個長度為1的子序列龄句。
分析完了回论，上圖：(第二列表示前i個數(shù)中LIS的長度散罕， 第三列表示，LIS中到達當前這個數(shù)的上一個數(shù)的下標傀蓉，根據(jù)這個可以求出LIS序列)
我的代碼：
該算法的時間復雜度是O(n^2 )欧漱，并不是最優(yōu)的解法。 還有一種很巧妙的算法可以將時間復雜度降到O(nlogn)葬燎，網(wǎng)上已經(jīng)有各種文章介紹它误甚， 這里就不再贅述。傳送門：
important:先讀我的注好了谱净，非常推薦
最長遞增子序列 O(NlogN)算法 - Felix021 - 將所有歡脫傾翻?www.felix021.com
注：我決定重述一下窑邦，也許結合起來你就能夠明白這個優(yōu)化
這個優(yōu)化的核心在于二分法(事實上很多一維數(shù)據(jù)結構的logN優(yōu)化都是二分法)，關鍵是真正建立一個有序列表A壕探，來存儲當前步驟的LIS子序列冈钦，可優(yōu)化的是找到一個可以修改
練習題
無向圖G有N個結點(1<N<=1000)及一些邊，每一條邊上帶有正的權重值李请。 找到結點1到結點N的最短路徑瞧筛，或者輸出不存在這樣的路徑。
提示：在每一步中导盅，對于那些沒有計算過的結點驾窟， 及那些已經(jīng)計算出從結點1到它的最短路徑的結點，如果它們間有邊认轨， 則計算從結點1到未計算結點的最短路徑绅络。
嘗試解決以下來自topcoder競賽的問題：
ZigZag - 2003 TCCC Semifinals 3
BadNeighbors - 2004 TCCC Round 4
FlowerGarden - 2004 TCCC Round 1
中級（這個看看就行了，不要寫代碼）
注：這個可以幫我們理解最簡單的二維問題嘁字，但是沒有給量化的蘋果樹恩急，寫代碼的價值不大。
接下來纪蜒，讓我們來看看如何解決二維的DP問題衷恭。
平面上有N*M個格子，每個格子中放著一定數(shù)量的蘋果纯续。你從左上角的格子開始随珠， 每一步只能向下走或是向右走，每次走到一個格子上就把格子里的蘋果收集起來猬错， 這樣下去窗看，你最多能收集到多少個蘋果。
解這個問題與解其它的DP問題幾乎沒有什么兩樣倦炒。第一步找到問題的“狀態(tài)”显沈， 第二步找到“狀態(tài)轉移方程”，然后基本上問題就解決了。
首先拉讯，我們要找到這個問題中的“狀態(tài)”是什么涤浇？我們必須注意到的一點是， 到達一個格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)魔慷。 因此為了求出到達當前格子后最多能收集到多少個蘋果只锭， 我們就要先去考察那些能到達當前這個格子的格子，到達它們最多能收集到多少個蘋果院尔。 (是不是有點繞蜻展，但這句話的本質其實是DP的關鍵：欲求問題的解，先要去求子問題的解)
經(jīng)過上面的分析召边，很容易可以得出問題的狀態(tài)和狀態(tài)轉移方程铺呵。 狀態(tài)S[i][j]表示我們走到(i, j)這個格子時裹驰，最多能收集到多少個蘋果隧熙。那么， 狀態(tài)轉移方程如下：
S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)
其中i代表行幻林，j代表列贞盯，下標均從0開始；A[i][j]代表格子(i, j)處的蘋果數(shù)量沪饺。
S[i][j]有兩種計算方式：1.對于每一行躏敢，從左向右計算，然后從上到下逐行處理整葡；2. 對于每一列件余，從上到下計算，然后從左向右逐列處理遭居。 這樣做的目的是為了在計算S[i][j]時啼器，S[i-1][j]和S[i][j-1]都已經(jīng)計算出來了。
偽代碼如下：
以下兩道題來自topcoder俱萍，練習用的端壳。
AvoidRoads - 2003 TCO Semifinals 4
ChessMetric - 2003 TCCC Round 4
中高級
這一節(jié)要討論的是帶有額外條件的DP問題。
以下的這個問題是個很好的例子枪蘑。
無向圖G有N個結點损谦，它的邊上帶有正的權重值。
你從結點1開始走岳颇，并且一開始的時候你身上帶有M元錢照捡。如果你經(jīng)過結點i， 那么你就要花掉S[i]元(可以把這想象為收過路費)话侧。如果你沒有足夠的錢麻敌， 就不能從那個結點經(jīng)過。在這樣的限制條件下掂摔，找到從結點1到結點N的最短路徑术羔。 或者輸出該路徑不存在赢赊。如果存在多條最短路徑，那么輸出花錢數(shù)量最少的那條级历。 限制：1<N<=100 ; 0<=M<=100 ; 對于每個i释移，0<=S[i]<=100；正如我們所看到的寥殖， 如果沒有額外的限制條件(在結點處要收費玩讳，費用不足還不給過)，那么嚼贡， 這個問題就和經(jīng)典的迪杰斯特拉問題一樣了(找到兩結點間的最短路徑)熏纯。 在經(jīng)典的迪杰斯特拉問題中， 我們使用一個一維數(shù)組來保存從開始結點到每個結點的最短路徑的長度粤策， 即M[i]表示從開始結點到結點i的最短路徑的長度樟澜。然而在這個問題中， 我們還要保存我們身上剩余多少錢這個信息叮盘。因此秩贰，很自然的， 我們將一維數(shù)組擴展為二維數(shù)組柔吼。M[i][j]表示從開始結點到結點i的最短路徑長度毒费， 且剩余j元。通過這種方式愈魏，我們將這個問題規(guī)約到原始的路徑尋找問題觅玻。 在每一步中，對于已經(jīng)找到的最短路徑培漏，我們找到它所能到達的下一個未標記狀態(tài)(i,j)溪厘， 將它標記為已訪問(之后不再訪問這個結點)，并且在能到達這個結點的各個最短路徑中北苟， 找到加上當前邊權重值后最小值對應的路徑桩匪，即為該結點的最短路徑。 (寫起來真是繞友鼻，建議畫個圖就會明了很多)傻昙。不斷重復上面的步驟， 直到所有的結點都訪問到為止(這里的訪問并不是要求我們要經(jīng)過它彩扔， 比如有個結點收費很高妆档，你沒有足夠的錢去經(jīng)過它，但你已經(jīng)訪問過它) 最后Min[N-1][j]中的最小值即是問題的答案(如果有多個最小值虫碉， 即有多條最短路徑贾惦，那么選擇j最大的那條路徑，即，使你剩余錢數(shù)最多的最短路徑)须板。
偽代碼：
下面有幾道topcoder上的題以供練習：
Jewelry - 2003 TCO Online Round 4
StripePainter - SRM 150 Div 1
QuickSums - SRM 197 Div 2
ShortPalindromes - SRM 165 Div 2
高級
以下問題需要仔細的揣摩才能將其規(guī)約為可用DP解的問題碰镜。
問題：StarAdventure - SRM 208 Div 1:
給定一個M行N列的矩陣(M*N個格子)，每個格子中放著一定數(shù)量的蘋果习瑰。 你從左上角的格子開始绪颖，只能向下或向右走，目的地是右下角的格子甜奄。 你每走過一個格子柠横，就把格子上的蘋果都收集起來。然后你從右下角走回左上角的格子课兄， 每次只能向左或是向上走牍氛，同樣的，走過一個格子就把里面的蘋果都收集起來烟阐。 最后搬俊，你再一次從左上角走到右下角，每過一個格子同樣要收集起里面的蘋果 (如果格子里的蘋果數(shù)為0曲饱，就不用收集)悠抹。求你最多能收集到多少蘋果珠月。
注意：當你經(jīng)過一個格子時扩淀，你要一次性把格子里的蘋果都拿走。
限制條件：1 < N, M <= 50啤挎；每個格子里的蘋果數(shù)量是0到1000(包含0和1000)驻谆。
如果我們只需要從左上角的格子走到右下角的格子一次，并且收集最大數(shù)量的蘋果庆聘， 那么問題就退化為“中級”一節(jié)里的那個問題胜臊。將這里的問題規(guī)約為“中級”里的簡單題， 這樣一來會比較好解伙判。讓我們來分析一下這個問題象对，要如何規(guī)約或是修改才能用上DP。 首先宴抚，對于第二次從右下角走到左上角得出的這條路徑勒魔， 我們可以將它視為從左上角走到右下角得出的路徑，沒有任何的差別菇曲。 (即從B走到A的最優(yōu)路徑和從A走到B的最優(yōu)路徑是一樣的)通過這種方式冠绢， 我們得到了三條從頂走到底的路徑。對于這一點的理解可以稍微減小問題的難度常潮。 于是弟胀，我們可以將這3條路徑記為左，中，右路徑孵户。對于兩條相交路徑(如下圖)：
在不影響結果的情況下萧朝，我們可以將它們視為兩條不相交的路徑：
這樣一來，我們將得到左夏哭，中剪勿，右3條路徑。此外方庭，如果我們要得到最優(yōu)解厕吉， 路徑之間不能相交(除了左上角和右下角必然會相交的格子)。因此對于每一行y( 除了第一行和最后一行)械念，三條路徑對應的x坐標要滿足：x1[y] < x2[y] < x3[y]头朱。 經(jīng)過這一步的分析，問題的DP解法就進一步地清晰了龄减。讓我們考慮行y项钮， 對于每一個x1[y-1]，x2[y-1]和x3[y-1]希停，我們已經(jīng)找到了能收集到最多蘋果數(shù)量的路徑烁巫。 根據(jù)它們，我們能求出行y的最優(yōu)解〕枘埽現(xiàn)在我們要做的就是找到從一行移動到下一行的方式亚隙。 令Max[i][j][k]表示到第y-1行為止收集到蘋果的最大數(shù)量， 其中3條路徑分別止于第i,j,k列违崇。對于下一行y阿弃，對每個Max[i][j][k] 都加上格子(y,i)，(y,j)和(y,k)內的蘋果數(shù)量羞延。因此渣淳，每一步我們都向下移動。 我們做了這一步移動之后伴箩，還要考慮到入愧，一條路徑是有可能向右移動的。 (對于每一個格子嗤谚，我們有可能是從它上面向下移動到它棺蛛， 也可能是從它左邊向右移動到它)。為了保證3條路徑互不相交呵恢， 我們首先要考慮左邊的路徑向右移動的情況鞠值，然后是中間，最后是右邊的路徑渗钉。 為了更好的理解彤恶，讓我們來考慮左邊的路徑向右移動的情況钞钙，對于每一個可能的j,k對(j<k)， 對每個i(i<j)声离，考慮從位置(i-1,j,k)移動到位置(i,j,k)芒炼。處理完左邊的路徑， 再處理中間的路徑术徊，最后處理右邊的路徑本刽。方法都差不多。
用于練習的topcoder題目：
- MiniPaint - SRM 178 Div 1
其它
當閱讀一個題目并且開始嘗試解決它時赠涮，首先看一下它的限制子寓。 如果要求在多項式時間內解決，那么該問題就很可能要用DP來解笋除。遇到這種情況斜友， 最重要的就是找到問題的“狀態(tài)”和“狀態(tài)轉移方程”。(狀態(tài)不是隨便定義的垃它， 一般定義完狀態(tài)鲜屏，你要找到當前狀態(tài)是如何從前面的狀態(tài)得到的， 即找到狀態(tài)轉移方程)如果看起來是個DP問題国拇，但你卻無法定義出狀態(tài)洛史， 那么試著將問題規(guī)約到一個已知的DP問題(正如“高級”一節(jié)中的例子一樣)。
原創(chuàng)部分extraction：
對于背包問題我的答案：
這個方法沒有用循環(huán)來折疊酱吝，可能對萌新來說好理解一點也殖，可以參考一下恩商。
對于LIS問題我的答案：
優(yōu)化后的答案：
補充：更新了Graph中的錯誤，多源最短路徑的復雜度不是NP耀怜，只需要比較路徑讶凉。
Wallace QIAN：翹起二郎腿坐一下午就差不多能入門的 - 圖論?zhuanlan.zhihu.com
