本文針對兩篇優(yōu)秀動態(tài)規(guī)劃文章中存在的不易理解的部分：狀態(tài)岔擂、狀態(tài)轉(zhuǎn)移的定義和狀態(tài)轉(zhuǎn)移方程的編程實現(xiàn)部分進行個人解讀位喂。歡迎指出本文存在的錯誤和表述不清之處。
DP概述
DP(Dynamic Programming)是算法設(shè)計中解決最優(yōu)化問題(eg: 最長公共子序列)的重要思想乱灵。
（待補充）
因此我們可以得出結(jié)論:
動態(tài)規(guī)劃的本質(zhì)塑崖，是對問題狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的定義。
——什么是動態(tài)規(guī)劃阔蛉？動態(tài)規(guī)劃的意義是什么弃舒？(徐凱強 Andy的回答)
狀態(tài)
這里給出我自己的一個定義后面會解釋：
從“原始的最優(yōu)化問題”剝離出的每個“最優(yōu)化子問題”都是當前DP問題的一個狀態(tài)癞埠，每個狀態(tài)分布在“每次的決策前后”状原。
我們現(xiàn)在來看兩個簡單的動態(tài)規(guī)劃問題：
問題1：
給定一個數(shù)列A，長度為N苗踪，
求這個數(shù)列的最長上升（遞增）子數(shù)列（LIS）的長度.
以
1 7 2 8 3 4
為例颠区。
這個數(shù)列的最長遞增子數(shù)列是 1 2 3 4，長度為4通铲；
次長的長度為3毕莱， 包括 1 7 8; 1 2 3 等.
剝離出的子問題，以及等價最終問題：
給定一個數(shù)列A颅夺，長度為N
設(shè)F(x)：以數(shù)列A中第x項結(jié)尾的最長遞增子序列的長度, 其中0 <= x <= N 朋截。(子問題or狀態(tài))
求F(1)..F(N)中的最大值 (等價最終問題)
問題2:
如果我們有面值為1元、3元和5元的硬幣若干枚吧黄，如何用最少的硬幣湊夠11元部服？
剝離出的子問題，以及等價最終問題：
如果我們有面值為1元拗慨、3元和5元的硬幣若干枚
設(shè)D(i)：湊夠i元使用最少硬幣個數(shù)廓八，其中 0 <= i <= 11。(子問題or狀態(tài))
求D(11)的值赵抢。 (等價最終問題)
這兩個問題便是“原始的最優(yōu)化問題”【珲澹現(xiàn)在，根據(jù)“狀態(tài)和狀態(tài)轉(zhuǎn)移方程的定義是動態(tài)規(guī)劃的本質(zhì)”的結(jié)論烦却，我們需要做的就是從“原始的最優(yōu)化問題”中找出狀態(tài)宠叼，然后再得到狀態(tài)轉(zhuǎn)移方程，之后根據(jù)狀態(tài)轉(zhuǎn)移方程實現(xiàn)代碼(其間還會使用到記憶和重疊子問題特性)其爵，最終得到解车吹。
-
剝離子問題筹裕，獲得狀態(tài)(最需要技巧和訓練的部分)
之前說過，DP中的狀態(tài)就是子問題窄驹。顯然朝卒，我們要獲得狀態(tài)就必須剝離(拆分)“原始的最優(yōu)化問題”。這里通過分析問題1和問題2剝離好的子問題探索一下DP中剝離（拆分）問題的“奇淫巧技”乐埠。首先拿到一個DP問題抗斤，我們最先要思考的是: 該問題的“變數(shù)”在哪里？這里的“變數(shù)”很重要丈咐，問題的“變數(shù)”往往是整個問題定義中的一個參數(shù)瑞眼，當我們改變這個參數(shù)時，將會使問題的規(guī)目醚罚縮小伤疙。 例如，問題1的變數(shù)是數(shù)列A的大小辆影，當我們改變數(shù)列A的大小時徒像，問題1的規(guī)模變縮小了。因此蛙讥，我們才這樣剝離問題1:"F(x)是以A[x]為結(jié)尾的LIS的長度锯蛀，且 0<= x <= N"。顯然次慢，此時若x 等于 N-1旁涤，我們把問題縮小了單位1長度；此時若x等于0迫像，我們則把問題縮小成了0劈愚，顯然此時還觸碰到了當前問題的邊界：“數(shù)列長度必須大于等于0”。問題2中也可套用同樣的思路: 我們可以把最終需要湊夠的價格i元作為變數(shù)闻妓，當我們改變i元的大小時菌羽，問題2的規(guī)模同樣被縮小了。因此我們才這樣重新定義問題2:"D(i)是湊夠i元需要的最少硬幣個數(shù)"纷闺。此時若i等于0算凿，我們同樣到達了當前問題的邊界:"湊錢不可能湊出負數(shù)"。
因此犁功，DP剝離子問題需要多聯(lián)系"當前問題中可能的變數(shù)"氓轰，同時多加練習。
DP中每個子問題都是狀態(tài)浸卦，分布在每次決策前后
把DP中的子問題問題叫做狀態(tài)有兩方面原因膳犹。為了區(qū)分問題和子問題而產(chǎn)生的叫法般贼。
之所以把Fx叫做“狀態(tài)”而不是“問題” 策彤，一是因為避免跟原問題中“問題”混淆，二是因為這個新問題是數(shù)學化定義的时捌。
——什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃的意義是什么炉抒？(徐凱強 Andy的回答)
- 狀態(tài)二詞更能準確表示出DP子問題是什么
從前面對剝離子問題的分析大抵可以感受到這么一個過程: 整個DP問題從問題的定義邊界開始(比如: 數(shù)列之長度為0奢讨，湊錢之總額為0)，到問題收斂處為止(比如: 數(shù)列之長度為N焰薄，湊錢之總額為0)拿诸，算法的每次決策都在推動前一個子問題發(fā)展到后一個子問題，往往這種推動都有多種可能性
比如:A={1 7 2 8 3 4}塞茅，從當前F(3)={1亩码，2}到F(6)時，我們可以很機智地選擇從F(5) = {1,2,3}走最優(yōu)解到F(6)={1,2,3,4}野瘦。但我們也可以任性地選擇F(5)={1,2}到F(6)={1,2,4}描沟，或者F(5)={1,2,3},F(6)={1,2,3}..以及其他多種可能性)。此時我們可以在子問題之間以不同的狀態(tài)(如F(5)={1,2,3} 或者F(5)={1,2})進行轉(zhuǎn)移(比如從F(5)={1,2,3}到F(6)={1,2,3,4})鞭光，因此把子問題叫做“狀態(tài)”吏廉，把子問題間的轉(zhuǎn)移叫做“狀態(tài)轉(zhuǎn)移”是很形象的說辭。
狀態(tài)轉(zhuǎn)移方程
對狀態(tài)的解釋已經(jīng)觸及到了狀態(tài)轉(zhuǎn)移的概念:“子問題間通過決策進行推演的過程叫做狀態(tài)轉(zhuǎn)移”衰猛。所以迟蜜，狀態(tài)轉(zhuǎn)移方程就應該是“子問題間通過決策定義的等式關(guān)系叫做狀態(tài)轉(zhuǎn)移方程”刹孔，通常狀態(tài)轉(zhuǎn)移方程和當前問題的邊界條件聯(lián)立起來叫做狀態(tài)轉(zhuǎn)移方程式啡省。
——什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃的意義是什么髓霞？(徐凱強 Andy的回答)
——動態(tài)規(guī)劃：從新手到專家
顯然卦睹，max(), min()就代表著一種最優(yōu)決策。我們?nèi)绻裮ax或者min去掉方库，那么上面的方程式依然可以叫做狀態(tài)轉(zhuǎn)移方程结序，只是得到的結(jié)果不一定是最優(yōu)解了。
編程實現(xiàn)
初學者在解DP問題時纵潦，如何編程實現(xiàn)狀態(tài)轉(zhuǎn)移方程徐鹤？如何在DP求解過程中利用重疊子問題進行記憶求解？
讓我們看一下問題2的偽代碼:
從偽代碼我們可以分析出一個較為通用的DP代碼實現(xiàn)過程：（S代表總額邀层，N-1代表可能的硬幣面值）
- 首先我們需要存儲每個子問題的最優(yōu)解返敬，比如偽代碼中使用Min[i]數(shù)組存儲每個子問題的最優(yōu)解。
- 然后我們需要對DP問題的邊界的解進行初始化寥院，比如偽代碼中Min[0] = 0代表著邊界條件"湊夠0元需要的最少硬幣數(shù)"的解劲赠。
- 定義好邊界解后，我們就可以從邊界解開始，使用遞歸的方法自底向上的求解DP的每個子問題凛澎，并把子問題的最優(yōu)解記錄下來霹肝。比如，偽代碼中從i = 1開始求解直到i = s,每次得到的子問題最優(yōu)解都被存儲在Min[i]中塑煎。
- 最后沫换，根據(jù)特定的題目，或直接輸出某個子問題的最優(yōu)解最铁，或?qū)λ凶訂栴}的最優(yōu)解進行處理以后再進行輸出苗沧。比如：硬幣問題我們可以直接輸出Min[11]。而LIS問題我們需要比較F(x),x = 0,1,2...N炭晒， 然后輸出F(x)的最大值待逞。
引用
什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃的意義是什么网严？
http://www.hawstein.com/posts/dp-novice-to-advanced.html
動態(tài)規(guī)劃：從新手到專家
https://www.zhihu.com/question/23995189
