作者：阮行止
鏈接：https://www.zhihu.com/question/23995189/answer/613096905
來源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)靶衍，非商業(yè)轉(zhuǎn)載請注明出處灾炭。
0. intro
很有意思的問題。以往見過許多教材颅眶，對動(dòng)態(tài)規(guī)劃（DP）的引入屬于“奉天承運(yùn)蜈出，皇帝詔曰”式：不給出一點(diǎn)引入，見面即拿出一大堆公式嚇人涛酗；學(xué)生則死啃書本铡原，然后突然頓悟。針對入門者的教材不應(yīng)該是這樣的商叹。恰好我給入門者講過四次DP入門燕刻，迭代出了一套比較靠譜的教學(xué)方法，所以今天跑過來獻(xiàn)丑剖笙。
現(xiàn)在卵洗，我們試著自己來一步步“重新發(fā)明”DP。
1. 從一個(gè)生活問題談起
先來看看生活中經(jīng)常遇到的事吧——假設(shè)您是個(gè)土豪弥咪，身上帶了足夠的1过蹂、5十绑、10、20榴啸、50孽惰、100元面值的鈔票。現(xiàn)在您的目標(biāo)是湊出某個(gè)金額w鸥印，需要用到盡量少的鈔票。
依據(jù)生活經(jīng)驗(yàn)坦报，我們顯然可以采取這樣的策略：能用100的就盡量用100的库说，否則盡量用50的……依次類推。在這種策略下片择，666=6×100+1×50+1×10+1×5+1×1潜的，共使用了10張鈔票。
這種策略稱為“貪心”：假設(shè)我們面對的局面是“需要湊出w”字管，貪心策略會(huì)<u>盡快</u>讓w變得更小啰挪。能讓w少100就盡量讓它少100，這樣我們接下來面對的局面就是湊出w-100嘲叔。長期的生活經(jīng)驗(yàn)表明亡呵，貪心策略是正確的。
但是硫戈，如果我們換一組鈔票的面值锰什，貪心策略就也許不成立了。如果一個(gè)奇葩國家的鈔票面額分別是1丁逝、5汁胆、11，那么我們在湊出15的時(shí)候霜幼，貪心策略會(huì)出錯(cuò)：
15=1×11+4×1 （貪心策略使用了5張鈔票）
15=3×5 （正確的策略嫩码，只用3張鈔票）
為什么會(huì)這樣呢？貪心策略錯(cuò)在了哪里罪既？
鼠目寸光铸题。
剛剛已經(jīng)說過，貪心策略的綱領(lǐng)是：“盡量使接下來面對的w更小”萝衩。這樣回挽，貪心策略在w=15的局面時(shí)，會(huì)優(yōu)先使用11來把w降到4猩谊；但是在這個(gè)問題中千劈，湊出4的代價(jià)是很高的，必須使用4×1牌捷。如果使用了5墙牌，w會(huì)降為10涡驮，雖然沒有4那么小，但是湊出10只需要兩張5元喜滨。
在這里我們發(fā)現(xiàn)捉捅，貪心是一種只考慮眼前情況的策略。
那么虽风，現(xiàn)在我們怎樣才能避免鼠目寸光呢棒口？
如果直接暴力枚舉湊出w的方案，明顯復(fù)雜度過高辜膝。太多種方法可以湊出w了无牵，枚舉它們的時(shí)間是不可承受的。我們現(xiàn)在來嘗試找一下性質(zhì)厂抖。
重新分析剛剛的例子茎毁。w=15時(shí)，我們?nèi)绻?1忱辅，接下來就面對w=4的情況七蜘；如果取5，則接下來面對w=10的情況墙懂。我們發(fā)現(xiàn)這些問題都有相同的形式：“給定w橡卤，湊出w所用的最少鈔票是多少張？”接下來垒在，我們用f(n)來表示“湊出n所需的最少鈔票數(shù)量”蒜魄。
那么，如果我們?nèi)×?1场躯，最后的代價(jià)（用掉的鈔票總數(shù)）是多少呢谈为？
明顯
，它的意義是：利用11來湊出15踢关，付出的代價(jià)等于f(4)加上自己這一張鈔票∩■辏現(xiàn)在我們暫時(shí)不管f(4)怎么求出來。
依次類推签舞，馬上可以知道：如果我們用5來湊出15秕脓，cost就是[圖片上傳失敗...(image-92136e-1553889175909)]
。
那么儒搭，現(xiàn)在w=15的時(shí)候吠架，我們該取那種鈔票呢？當(dāng)然是各種方案中搂鲫，cost值最低的那一個(gè)傍药！
- 取11：[圖片上傳失敗...(image-449a18-1553889175909)]
- 取5： [圖片上傳失敗...(image-16df1-1553889175909)]
- 取1： [圖片上傳失敗...(image-b7bb09-1553889175909)]
顯而易見，cost值最低的是取5的方案。我們通過上面三個(gè)式子拐辽，做出了正確的決策拣挪！
這給了我們一個(gè)至關(guān)重要的啟示—— [圖片上傳失敗...(image-e50dbf-1553889175909)]
只與 [圖片上傳失敗...(image-9bcd8c-1553889175909)]
相關(guān)；更確切地說：
[圖片上傳失敗...(image-8c27c8-1553889175909)]
這個(gè)式子是非常激動(dòng)人心的俱诸。我們要求出f(n)菠劝，只需要求出幾個(gè)更小的f值；既然如此睁搭，我們從小到大把所有的f(i)求出來不就好了赶诊？注意一下邊界情況即可。代碼如下：
<noscript><img src="https://pic2.zhimg.com/50/v2-6a5ba74fb90968533ece429ed329c903_hd.jpg" data-rawwidth="1044" data-rawheight="440" data-size="normal" data-caption="" data-default-watermark-src="https://pic2.zhimg.com/50/v2-af8977bff8d8e7f41d72b2e0416c83d6_hd.jpg" class="origin_image zh-lightbox-thumb" width="1044" data-original="https://pic2.zhimg.com/v2-6a5ba74fb90968533ece429ed329c903_r.jpg"/></noscript>
我們以 [圖片上傳失敗...(image-74d57e-1553889175909)]
的復(fù)雜度解決了這個(gè)問題≡奥妫現(xiàn)在回過頭來甫何，我們看看它的原理：
- [圖片上傳失敗...(image-394a5b-1553889175909)]
只與[圖片上傳失敗...(image-e12d46-1553889175909)]
的值相關(guān)。
- 我們只關(guān)心 [圖片上傳失敗...(image-9bd106-1553889175909)]
的值遇伞，不關(guān)心是怎么湊出w的。
這兩個(gè)事實(shí)捶牢，保證了我們做法的正確性鸠珠。它比起貪心策略，會(huì)分別算出取1秋麸、5渐排、11的代價(jià)，從而做出一個(gè)正確決策灸蟆，這樣就避免掉了“鼠目寸光”驯耻！
它與暴力的區(qū)別在哪里？我們的暴力枚舉了“使用的硬幣”炒考，然而這屬于冗余信息可缚。我們要的是答案，根本不關(guān)心這個(gè)答案是怎么湊出來的斋枢。譬如帘靡，要求出f(15)，只需要知道f(14),f(10),f(4)的值瓤帚。其他信息并不需要描姚。我們舍棄了冗余信息。我們只記錄了對解決問題有幫助的信息——f(n).
我們能這樣干戈次，取決于問題的性質(zhì)：求出f(n)轩勘，只需要知道幾個(gè)更小的f(c)。我們將求解f(c)稱作求解f(n)的“子問題”怯邪。
這就是DP（動(dòng)態(tài)規(guī)劃绊寻，dynamic programming）.
將一個(gè)問題拆成幾個(gè)子問題，分別求解這些子問題，即可推斷出大問題的解榛斯。
思考題：請稍微修改代碼观游，輸出我們湊出w的方案。
2. 幾個(gè)簡單的概念
【無后效性】
一旦f(n)確定驮俗，“我們?nèi)绾螠惓鰂(n)”就再也用不著了懂缕。
要求出f(15)，只需要知道f(14),f(10),f(4)的值王凑，而f(14),f(10),f(4)是如何算出來的搪柑，對之后的問題沒有影響。
“未來與過去無關(guān)”索烹，這就是無后效性工碾。
（嚴(yán)格定義：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響百姓。）
【最優(yōu)子結(jié)構(gòu)】
回顧我們對f(n)的定義：我們記“湊出n所需的最少鈔票數(shù)量”為f(n).
f(n)的定義就已經(jīng)蘊(yùn)含了“最優(yōu)”渊额。利用w=14,10,4的最優(yōu)解，我們即可算出w=15的最優(yōu)解垒拢。
大問題的最優(yōu)解可以由小問題的最優(yōu)解推出旬迹，這個(gè)性質(zhì)叫做“最優(yōu)子結(jié)構(gòu)性質(zhì)”。
引入這兩個(gè)概念之后求类，我們?nèi)绾闻袛嘁粋€(gè)問題能否使用DP解決呢奔垦？
能將大問題拆成幾個(gè)小問題，且滿足無后效性尸疆、最優(yōu)子結(jié)構(gòu)性質(zhì)椿猎。
3. DP的典型應(yīng)用：DAG最短路
問題很簡單：給定一個(gè)城市的地圖，所有的道路都是單行道寿弱，而且不會(huì)構(gòu)成環(huán)犯眠。每條道路都有過路費(fèi)，問您從S點(diǎn)到T點(diǎn)花費(fèi)的最少費(fèi)用脖捻。
<noscript><img src="https://pic1.zhimg.com/50/v2-38e9a487997d2eea979097fbc9e9e674_hd.jpg" data-rawwidth="523" data-rawheight="251" data-size="normal" data-default-watermark-src="https://pic3.zhimg.com/50/v2-4d9f5b84e0d1f8aafe616a36b869a012_hd.jpg" class="origin_image zh-lightbox-thumb" width="523" data-original="https://pic1.zhimg.com/v2-38e9a487997d2eea979097fbc9e9e674_r.jpg"/></noscript>
<figcaption>一張地圖阔逼。邊上的數(shù)字表示過路費(fèi)。</figcaption>
這個(gè)問題能用DP解決嗎地沮？我們先試著記從S到P的最少費(fèi)用為f(P).
想要到T嗜浮，要么經(jīng)過C，要么經(jīng)過D摩疑。從而[圖片上傳失敗...(image-c737c2-1553889175908)]
.
好像看起來可以DP∥Ｈ冢現(xiàn)在我們檢驗(yàn)剛剛那兩個(gè)性質(zhì)：
- 無后效性：對于點(diǎn)P，一旦f(P)確定雷袋，以后就只關(guān)心f(P)的值吉殃，不關(guān)心怎么去的辞居。
- 最優(yōu)子結(jié)構(gòu)：對于P，我們當(dāng)然只關(guān)心到P的最小費(fèi)用蛋勺，即f(P)瓦灶。如果我們從S走到T是 [圖片上傳失敗...(image-971307-1553889175906)]
，那肯定S走到Q的最優(yōu)路徑是 [圖片上傳失敗...(image-6fe1f6-1553889175906)]
抱完。對一條最優(yōu)的路徑而言贼陶，從S走到沿途上所有的點(diǎn)（子問題）的最優(yōu)路徑，都是這條大路的一部分巧娱。這個(gè)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是顯然的碉怔。
既然這兩個(gè)性質(zhì)都滿足，那么本題可以DP禁添。式子明顯為：
[圖片上傳失敗...(image-1f0de1-1553889175906)]
其中R為有路通到P的所有的點(diǎn)撮胧， [圖片上傳失敗...(image-da8176-1553889175906)]
為R到P的過路費(fèi)。
代碼實(shí)現(xiàn)也很簡單老翘，拓?fù)渑判蚣纯伞?/p>
4. 對DP原理的一點(diǎn)討論
【DP的核心思想】
DP為什么會(huì)快芹啥？
無論是DP還是暴力，我們的算法都是在可能解空間內(nèi)铺峭，尋找最優(yōu)解叁征。
來看鈔票問題。暴力做法是枚舉所有的可能解逛薇，這是最大的可能解空間。
DP是枚舉有希望成為答案的解疏虫。這個(gè)空間比暴力的小得多永罚。
也就是說：DP自帶剪枝。
DP舍棄了一大堆不可能成為最優(yōu)解的答案卧秘。譬如：
15 = 5+5+5 被考慮了呢袱。
15 = 5+5+1+1+1+1+1 從來沒有考慮過，因?yàn)檫@不可能成為最優(yōu)解翅敌。
從而我們可以得到DP的核心思想：盡量縮小可能解空間羞福。
在暴力算法中，可能解空間往往是指數(shù)級(jí)的大序卿獭治专；如果我們采用DP，那么有可能把解空間的大小降到多項(xiàng)式級(jí)遭顶。
一般來說张峰，解空間越小，尋找解就越快棒旗。這樣就完成了優(yōu)化喘批。
【DP的操作過程】
一言以蔽之：大事化小，小事化了。
將一個(gè)大問題轉(zhuǎn)化成幾個(gè)小問題饶深；
求解小問題餐曹；
推出大問題的解。
【如何設(shè)計(jì)DP算法】
下面介紹比較通用的設(shè)計(jì)DP算法的步驟敌厘。
首先台猴，把我們面對的局面表示為x。這一步稱為設(shè)計(jì)狀態(tài)额湘。
對于狀態(tài)x卿吐，記我們要求出的答案(e.g. 最小費(fèi)用)為f(x).我們的目標(biāo)是求出f(T).
找出f(x)與哪些局面有關(guān)（記為p），寫出一個(gè)式子（稱為狀態(tài)轉(zhuǎn)移方程）锋华，通過f(p)來推出f(x).
【DP三連】
設(shè)計(jì)DP算法嗡官，往往可以遵循DP三連：
我是誰？ ——設(shè)計(jì)狀態(tài)毯焕，表示局面
我從哪里來衍腥？
我要到哪里去？ ——設(shè)計(jì)轉(zhuǎn)移
設(shè)計(jì)狀態(tài)是DP的基礎(chǔ)纳猫。接下來的設(shè)計(jì)轉(zhuǎn)移婆咸，有兩種方式：一種是考慮我從哪里來（本文之前提到的兩個(gè)例子，都是在考慮“我從哪里來”）芜辕；另一種是考慮我到哪里去尚骄，這常見于求出f(x)之后，更新能從x走到的一些解侵续。這種DP也是不少的倔丈，我們以后會(huì)遇到。
總而言之状蜗，“我從哪里來”和“我要到哪里去”只需要考慮清楚其中一個(gè)需五，就能設(shè)計(jì)出狀態(tài)轉(zhuǎn)移方程，從而寫代碼求解問題轧坎。前者又稱pull型的轉(zhuǎn)移宏邮，后者又稱push型的轉(zhuǎn)移殉了。（這兩個(gè)詞是
妹妹告訴我的氨鹏，不知道源出處在哪）
思考題：如何把鈔票問題的代碼改寫成“我到哪里去”的形式壹无？
提示：求出f(x)之后错洁，更新f(x+1),f(x+5),f(x+11).
5. 例題：最長上升子序列
扯了這么多形而上的內(nèi)容滨达，還是做一道例題吧强经。
最長上升子序列（LIS）問題：給定長度為n的序列a厂榛，從a中抽取出一個(gè)子序列吕粹，這個(gè)子序列需要單調(diào)遞增族扰。問最長的上升子序列（LIS）的長度厌丑。
e.g. 1,5,3,4,6,9,7,8的LIS為1,3,4,6,7,8定欧，長度為6。
如何設(shè)計(jì)狀態(tài)（我是誰）怒竿？
我們記 [圖片上傳失敗...(image-217ef8-1553889175905)]
為以 [圖片上傳失敗...(image-8e356c-1553889175905)]
結(jié)尾的LIS長度砍鸠，那么答案就是 [圖片上傳失敗...(image-2a5b3-1553889175905)]
.
狀態(tài)x從哪里推過來（我從哪里來）？
考慮比x小的每一個(gè)p：如果 [圖片上傳失敗...(image-d1a86c-1553889175905)]
耕驰，那么f(x)可以取f(p)+1.
解釋：我們把 [圖片上傳失敗...(image-a89795-1553889175905)]
接在 [圖片上傳失敗...(image-767dd8-1553889175905)]
的后面爷辱，肯定能構(gòu)造一個(gè)以 [圖片上傳失敗...(image-19f5e8-1553889175905)]
結(jié)尾的上升子序列，長度比以 [圖片上傳失敗...(image-780571-1553889175905)]
結(jié)尾的LIS大1.那么朦肘，我們可以寫出狀態(tài)轉(zhuǎn)移方程了：
[圖片上傳失敗...(image-186a20-1553889175905)]
至此解決問題饭弓。兩層for循環(huán)，復(fù)雜度 [圖片上傳失敗...(image-82d713-1553889175905)]
.
<noscript><img src="https://pic3.zhimg.com/50/v2-73ea19922aaac11c15dff9146a5c5b41_hd.jpg" data-rawwidth="883" data-rawheight="455" data-size="normal" data-caption="" data-default-watermark-src="https://pic2.zhimg.com/50/v2-ce272e9f786ef6377691df709264711a_hd.jpg" class="origin_image zh-lightbox-thumb" width="883" data-original="https://pic3.zhimg.com/v2-73ea19922aaac11c15dff9146a5c5b41_r.jpg"/></noscript>
從這三個(gè)例題中可以看出媒抠，DP是一種思想弟断，一種“大事化小，小事化了”的思想趴生。帶著這種思想阀趴，DP將會(huì)成為我們解決問題的利器。
最后苍匆，我們一起念一遍DP三連吧——我是誰刘急？我從哪里來？我要到哪里去浸踩？
6. 習(xí)題
如果讀者有興趣叔汁，可以試著完成下面幾個(gè)習(xí)題：
一、請采取一些優(yōu)化手段检碗，以 [圖片上傳失敗...(image-80a8e7-1553889175905)]
的復(fù)雜度解決LIS問題攻柠。
提示：可以參考這篇博客 Junior Dynamic Programming--動(dòng)態(tài)規(guī)劃初步·各種子序列問題
二、“按順序遞推”和“記憶化搜索”是實(shí)現(xiàn)DP的兩種方式后裸。請查閱資料，簡單描述“記憶化搜索”是什么冒滩。并采用記憶化搜索寫出鈔票問題的代碼微驶，然后完成P1541 烏龜棋 - 洛谷 。
三开睡、01背包問題是一種常見的DP模型因苹。請完成P1048 采藥 - 洛谷。
