今天，你AI了沒？
編者按：本文可能是對動態規劃講的最易懂深刻的文章之一。
前言：以往見過許多教材，對動態規劃（DP）的引入屬于“奉天承運，皇帝昭曰”式：不給出一點引入，見面即拿出一大堆公式嚇人；學生則死啃書本，然后突然頓悟。針對入門者的教材不應該是這樣的。恰好我給入門者講過四次DP入門，迭代出了一套比較靠譜的教學方法，所以今天跑過來獻丑。現在我們試著自己來一步步“重新發明”DP。
從一個生活問題談起
先來看看生活中經常遇到的事吧——假設您是個土豪，身上帶了足夠的1、5、10、20、50、100元面值的鈔票。現在您的目標是湊出某個金額w，需要用到盡量少的鈔票。
依據生活經驗，我們顯然可以采取這樣的策略：能用100的就盡量用100的，否則盡量用50的……依次類推。在這種策略下，666=6×100 1×50 1×10 1×5 1×1，共使用了10張鈔票。
這種策略稱為“貪心”：假設我們面對的局面是“需要湊出w”，貪心策略會盡快讓w變得更小。能讓w少100就盡量讓它少100，這樣我們接下來面對的局面就是湊出w-100。長期的生活經驗表明，貪心策略是正確的。
但是，如果我們換一組鈔票的面值，貪心策略就也許不成立了。如果一個奇葩國家的鈔票面額分別是1、5、11，那么我們在湊出15的時候，貪心策略會出錯：
15=1×11 4×1 （貪心策略使用了5張鈔票）
15=3×5 （正確的策略，只用3張鈔票）
為什么會這樣呢？貪心策略錯在了哪里？
鼠目寸光。
剛剛已經說過，貪心策略的綱領是：“盡量使接下來面對的w更小”。這樣，貪心策略在w=15的局面時，會優先使用11來把w降到4；但是在這個問題中，湊出4的代價是很高的，必須使用4×1。如果使用了5，w會降為10，雖然沒有4那么小，但是湊出10只需要兩張5元。
在這里我們發現，貪心是一種只考慮眼前情況的策略。
那么，現在我們怎樣才能避免鼠目寸光呢？
如果直接暴力枚舉湊出w的方案，明顯復雜度過高。太多種方法可以湊出w了，枚舉它們的時間是不可承受的。我們現在來嘗試找一下性質。
重新分析剛剛的例子。w=15時，我們如果取11，接下來就面對w=4的情況；如果取5，則接下來面對w=10的情況。我們發現這些問題都有相同的形式：“給定w，湊出w所用的最少鈔票是多少張？”接下來，我們用f(n)來表示“湊出n所需的最少鈔票數量”。
那么，如果我們取了11，最后的代價（用掉的鈔票總數）是多少呢？
明顯
那么，現在w=15的時候，我們該取那種鈔票呢？當然是各種方案中，cost值最低的那一個！
顯而易見，cost值最低的是取5的方案。我們通過上面三個式子，做出了正確的決策！
這給了我們一個至關重要的啟示——
這個式子是非常激動人心的。我們要求出f(n)，只需要求出幾個更小的f值；既然如此，我們從小到大把所有的f(i)求出來不就好了？注意一下邊界情況即可。代碼如下：
我們以 O(n) 的復雜度解決了這個問題。現在回過頭來，我們看看它的原理：
這兩個事實，保證了我們做法的正確性。它比起貪心策略，會分別算出取1、5、11的代價，從而做出一個正確決策，這樣就避免掉了“鼠目寸光”！
它與暴力的區別在哪里？我們的暴力枚舉了“使用的硬幣”，然而這屬于冗余信息。我們要的是答案，根本不關心這個答案是怎么湊出來的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我們舍棄了冗余信息。我們只記錄了對解決問題有幫助的信息——f(n).
我們能這樣干，取決于問題的性質：求出f(n)，只需要知道幾個更小的f(c)。我們將求解f(c)稱作求解f(n)的“子問題”。
這就是DP（動態規劃，dynamic programming）.
將一個問題拆成幾個子問題，分別求解這些子問題，即可推斷出大問題的解。
思考題：請稍微修改代碼，輸出我們湊出w的方案。
【無后效性】
一旦f(n)確定，“我們如何湊出f(n)”就再也用不著了。
要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出來的，對之后的問題沒有影響。
“未來與過去無關”，這就是無后效性。
（嚴格定義：如果給定某一階段的狀態，則在這一階段以后過程的發展不受這階段以前各段狀態的影響。）
【最優子結構】
回顧我們對f(n)的定義：我們記“湊出n所需的最少鈔票數量”為f(n).
f(n)的定義就已經蘊含了“最優”。利用w=14,10,4的最優解，我們即可算出w=15的最優解。
大問題的最優解可以由小問題的最優解推出，這個性質叫做“最優子結構性質”。
引入這兩個概念之后，我們如何判斷一個問題能否使用DP解決呢？
能將大問題拆成幾個小問題，且滿足無后效性、最優子結構性質。
問題很簡單：給定一個城市的地圖，所有的道路都是單行道，而且不會構成環。每條道路都有過路費，問您從S點到T點花費的最少費用。
這個問題能用DP解決嗎？我們先試著記從S到P的最少費用為f(P).
想要到T，要么經過C，要么經過D。從而f(T)=min{f(C) 20,f(D) 10}.
好像看起來可以DP。現在我們檢驗剛剛那兩個性質：
- 無后效性：對于點P，一旦f(P)確定，以后就只關心f(P)的值，不關心怎么去的。
- 最優子結構：對于P，我們當然只關心到P的最小費用，即f(P)。如果我們從S走到T是 S->P->Q->T，那肯定S走到Q的最優路徑是S->P->Q。對一條最優的路徑而言，從S走到沿途上所有的點（子問題）的最優路徑，都是這條大路的一部分。這個問題的最優子結構性質是顯然的。
既然這兩個性質都滿足，那么本題可以DP。式子明顯為：
其中R為有路通到P的所有的點，WR->P 為R到P的過路費。
代碼實現也很簡單，拓撲排序即可。
【DP的核心思想】
DP為什么會快？
無論是DP還是暴力，我們的算法都是在可能解空間內，尋找最優解。
來看鈔票問題。暴力做法是枚舉所有的可能解，這是最大的可能解空間。
DP是枚舉有希望成為答案的解。這個空間比暴力的小得多。
也就是說：DP自帶剪枝。
DP舍棄了一大堆不可能成為最優解的答案。譬如：
15 = 5 5 5 被考慮了。
15 = 5 5 1 1 1 1 1 從來沒有考慮過，因為這不可能成為最優解。
從而我們可以得到DP的核心思想：盡量縮小可能解空間。
在暴力算法中，可能解空間往往是指數級的大小；如果我們采用DP，那么有可能把解空間的大小降到多項式級。
一般來說，解空間越小，尋找解就越快。這樣就完成了優化。
【DP的操作過程】
一言以蔽之：大事化小，小事化了。
將一個大問題轉化成幾個小問題；
求解小問題；
推出大問題的解。
【如何設計DP算法】
下面介紹比較通用的設計DP算法的步驟。
首先，把我們面對的局面表示為x。這一步稱為設計狀態。
對于狀態x，記我們要求出的答案(e.g. 最小費用)為f(x).我們的目標是求出f(T).
找出f(x)與哪些局面有關（記為p），寫出一個式子（稱為狀態轉移方程），通過f(p)來推出f(x).
【DP三連】
設計DP算法，往往可以遵循DP三連：
我是誰？ ——設計狀態，表示局面
我從哪里來？
我要到哪里去？ ——設計轉移
設計狀態是DP的基礎。接下來的設計轉移，有兩種方式：一種是考慮我從哪里來（本文之前提到的兩個例子，都是在考慮“我從哪里來”）；另一種是考慮我到哪里去，這常見于求出f(x)之后，更新能從x走到的一些解。這種DP也是不少的，我們以后會遇到。
總而言之，“我從哪里來”和“我要到哪里去”只需要考慮清楚其中一個，就能設計出狀態轉移方程，從而寫代碼求解問題。前者又稱pull型的轉移，后者又稱push型的轉移。
思考題：如何把鈔票問題的代碼改寫成“我到哪里去”的形式？
提示：求出f(x)之后，更新f(x 1),f(x 5),f(x 11).
如果讀者有興趣，可以試著完成下面幾個習題：
一、請采取一些優化手段，以
提示：可以參考這篇博客 Junior Dynamic Programming--動態規劃初步·各種子序列問題
地址：https://pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie
二、“按順序遞推”和“記憶化搜索”是實現DP的兩種方式。請查閱資料，簡單描述“記憶化搜索”是什么。并采用記憶化搜索寫出鈔票問題的代碼，然后完成P1541 烏龜棋 - 洛谷 。
地址：https://www.luogu.org/problemnew/show/P1541
三、01背包問題是一種常見的DP模型。請完成P1048 采藥 - 洛谷。
地址：https://www.luogu.org/problemnew/show/P1048
作者 | 阮行止
