目錄
1 動態(tài)規(guī)劃是什么
2 如何判斷一個問題可以使用動態(tài)規(guī)劃來解決
3 判斷要解決問題在動態(tài)規(guī)劃經(jīng)典問題中的分類
4 動態(tài)規(guī)劃的套路
5 如何進行優(yōu)化
6 案例分析

1. 動態(tài)規(guī)劃是什么

動態(tài)規(guī)劃（Dynamic programming，DP）是一種在數(shù)學(xué)、計算機科學(xué)和經(jīng)濟學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動態(tài)規(guī)劃方法所耗時間往往遠少于樸素解法。

動態(tài)規(guī)劃沒有實際的步驟來規(guī)定第一步做什么第二步做什么。所以更加確切的說，動態(tài)規(guī)劃是一種解決問題的思想。這種思想的本質(zhì)是，一個規(guī)模比較大的問題，是通過規(guī)模比較小的若干問題的結(jié)果來得到的（通過取最大，取最小，或者加起來之類的運算）。

大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用。

動態(tài)規(guī)劃一般是比較高效，那么相對低效的是什么呢？暴力搜索！動態(tài)規(guī)劃相對暴力搜索的優(yōu)點在于去掉了重復(fù)的計算量，可以通過直接獲取之前計算的結(jié)果來避免重復(fù)計算，這是動態(tài)規(guī)劃算法高效的重要原因。之前計算的結(jié)果都儲存在表格中，也就是動態(tài)規(guī)劃表。

動態(tài)規(guī)劃與遞歸可以對應(yīng)起來理解，前者是自底而上進行，后者是自頂而下進行搜索。同一個問題可能既可以用動態(tài)規(guī)劃解決，也可以使用遞歸解決。

動態(tài)規(guī)劃的核心代碼量通常在幾行到幾十行，包含狀態(tài)定義，狀態(tài)初始化，狀態(tài)轉(zhuǎn)移方程三大主要部分。

2. 如何判斷一個問題可以使用動態(tài)規(guī)劃來解決

發(fā)現(xiàn)一個問題適合用動態(tài)規(guī)劃解決非常重要，能堅定信念去找狀態(tài)轉(zhuǎn)移方程！

需要滿足兩個重要的特點。存在最優(yōu)子結(jié)構(gòu)和重疊性

最優(yōu)子結(jié)構(gòu)：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重要線索。（配題目來理解最優(yōu)子結(jié)構(gòu)）

重疊性：子問題重疊性質(zhì)是指在用遞歸算法自頂向下對問題進行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只計算一次，然后將其計算結(jié)果保存在一個表格中，當(dāng)再次需要計算已經(jīng)計算過的子問題時，只是在表格中簡單地查看一下結(jié)果，從而獲得較高的效率。（配圖對比自頂而下和自下而上，及幫助理解重疊性）

根據(jù)題目要求的答案，1. 求最大值/最小值2. 求可不可行3. 求方案總數(shù)，就有較大概率使用動態(tài)規(guī)劃。

3. 判斷要解決問題在動態(tài)規(guī)劃經(jīng)典問題中的分類

動態(tài)規(guī)劃問題種類的判斷正確（如判斷出是某個經(jīng)典問題或者是其變種），有助于快速分析出，狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程。

動態(tài)規(guī)劃問題的分類，一般可以按照問題中狀態(tài)的定義來分的，一維，雙一維，二維，區(qū)間，背包，劃分型。

動態(tài)規(guī)劃比較經(jīng)典的問題種類有，

遞推-斐波拉契數(shù)列，爬樓梯，

背包問題

最長遞增子序列LIS

最長公共子序列LCS

最小路徑和

最多路徑數(shù)

4. 動態(tài)規(guī)劃的套路

套路是固定的，分為4個部分。1定義狀態(tài)2推導(dǎo)狀態(tài)轉(zhuǎn)移方程3初始化狀態(tài)4問題要求的最后答案是什么

（1）狀態(tài)是什么，如何找到狀態(tài)

首先判斷狀態(tài)是哪一種？一維，雙一維，二維，區(qū)間，劃分型。有兩個難點。1是不容易看出來需要使用哪一種狀態(tài)。2是不容易定義，前i個元素，還是以第i個元素結(jié)尾的序列等。較簡單的比較容易能看得出來，有些題目不是那么容易看的出來的。一般而言，題目求什么，就定義狀態(tài)是什么。如果不容易定義，可以根據(jù)屬于哪一類經(jīng)典問題，參考進行定義。

（2）如何找狀態(tài)轉(zhuǎn)移方程

可以使用數(shù)學(xué)證明中的歸納法！

F[n]的定義

動態(tài)規(guī)劃的公式其實不難推，就那么幾種（下面四種）。如果這幾種套上去都搞不定，那么八成F[n]需要重新定義。

定義完畢，就要找F[n]和前面n步的關(guān)系了，分成四種，挨個套就行，難度由從低到高

a, F[n]跟前面一兩步有關(guān)

這種簡單

b, F[n]跟前面n步都有關(guān)

這種找到公式也不難，但要注意時間優(yōu)化了，不優(yōu)化往往就n^2了，舉例子《最長上升子序列》，代碼實現(xiàn)的過程中就需要借助for循環(huán)遍歷前面所有的狀態(tài)。

c, F[n]需要細分

這種情況下，你發(fā)現(xiàn)看著像，但是跟前面n步的關(guān)系整的你頭疼。

舉個例子，股票的幾個中等難度的題就是這樣。

那就把F[n]分成 F1[n] F2[n]，其實就是雙一維類型

d, F[n]，一維數(shù)組不夠用了

F[n]的細分其實是這個的簡單情況。

舉個例子，股票的狀態(tài)有出售，買入。那么F[n]再加一維數(shù)組，變成 F[n][]，第二緯只有0，1即可。二維比較難的，二維里面還區(qū)分劃分型。

對于二維的狀態(tài)方程，使用dp表更加簡潔明了，在對dp表進行初始化后，根據(jù)表格進行分析，更加容易找到規(guī)律。

在代碼實現(xiàn)的過程中，i起始的取值從1還是2開始，取決于等式右邊的索引不能為負，如果只有dp[i-1]，那可以從1開始；如果有dp[i-2]則只能從2開始。

如果當(dāng)前狀態(tài)與之前的所有狀態(tài)都有關(guān)，就會有兩層循環(huán)，內(nèi)層循環(huán)要遍歷之前的所有的狀態(tài)

（3）如何進行初始化

對于一維，通常會是dp[0],dp[1]可能要初始化，初始化的目的是為了保證dp[i]的索引不出現(xiàn)負數(shù)。狀態(tài)轉(zhuǎn)移方程dp[i]=……，等式右側(cè)中出現(xiàn)的如果只有dp[i-1]，則dp[0]初始化就行（索引i-1=0，i從1開始?。?，dp[1]可以推導(dǎo)出來；如果等式右側(cè)出現(xiàn)了dp[i-2]，則需要初始化dp[0],dp[1]（索引i-2=0，i=2，最小可以推導(dǎo)的是dp[2]）。

對于二維，可能需要對dp[0][j]，和dp[i][0]，即第一行和第一列進行初始化。同樣，如果出現(xiàn)了dp[i-2]的情況，也是需要對第二行和第二列進行初始化，不過一般都是只用初始化第一行和第一列。

在初始化的過程中，dp的長度也是個細節(jié)，有時與給定數(shù)組的長度相同，有時需要比給定數(shù)組的長度多一。這個是因為狀態(tài)方程中出現(xiàn)了dp[i+1]，為了使數(shù)組索引時不越界，要使得其長度+1.

有的狀態(tài)初始化其實在定義dp的時候就已經(jīng)完成了初始化，沒有專門的初始化代碼。

從狀態(tài)轉(zhuǎn)移方程的下標(biāo)思考初始化狀態(tài)，注意數(shù)組的下標(biāo)不能越界(上界和下界)，或者思考是否可以通過給狀態(tài)數(shù)組多加樣或一列，從而避免復(fù)雜的初始化討論！

（4）問題的答案

如果狀態(tài)的定義就是答案，通常就是dp[n]，如果不是就要根據(jù)具體的問題進行分析了，譬如有的是dp數(shù)組元素之和等等。

5. 如何進行優(yōu)化

動態(tài)規(guī)劃通常進行儲存空間上的優(yōu)化，這種優(yōu)化思想實際上是滾動數(shù)組(可以插入圖片)。

如果一維dp中，當(dāng)前狀態(tài)僅與某幾個狀態(tài)有關(guān)，則可以用變量來記錄相關(guān)狀態(tài)，空間復(fù)雜度降為O(1)。二維dp中，當(dāng)前狀態(tài)僅與某幾行或者某幾列有關(guān)，則可以用一維數(shù)組來記錄相關(guān)行列的狀態(tài)，空間復(fù)雜的杜降為O(n)（原來的空間復(fù)雜度是O(n*n)）。

假如狀態(tài)轉(zhuǎn)移方程如下：f[i][j] = f[i - 1][j] + f[i][j - 1]。我們可以發(fā)現(xiàn)，第i層的狀態(tài)，已經(jīng)和第i-2層的狀態(tài)沒有關(guān)系了，那么這種情況下，用于存儲第i-2層的空間就可以被重復(fù)利用。方法非常簡單，把數(shù)組的第一維對2取模就可以了：f[i % 2][j] = f[(i - 1) % 2][j] + f[i % 2][j-1]。這種方法通?？梢詫⒖臻g復(fù)雜度降低一個數(shù)量級。(如果用一維數(shù)組的話，狀態(tài)轉(zhuǎn)移公式的F(n)要分成2個，循環(huán)滾動)

image.png

6. 案例分析
案例是Leetcode上的題目，內(nèi)容較多，在此博文中進行總結(jié)
主要幫助理解最優(yōu)子結(jié)構(gòu)和重疊性，分析問題結(jié)構(gòu)看出可以采用動態(tài)規(guī)劃算法
理解狀態(tài)定義
理解如何找狀態(tài)轉(zhuǎn)移方程。

參考

動態(tài)規(guī)劃是什么
https://blog.csdn.net/cc_again/article/details/25866971

【干貨】動態(tài)規(guī)劃十問十答
https://zhuanlan.zhihu.com/p/26743197

狀態(tài)方程推導(dǎo)
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/dong-tai-gui-hua-shen-ru-fen-xi-by-wang-yan-19/

告別動態(tài)規(guī)劃，連刷 40 道題，我總結(jié)了這些套路，看不懂你打我（萬字長文）
https://zhuanlan.zhihu.com/p/91582909?utm_source=cn.ticktick.task&utm_medium=social&utm_oi=684404101006102528

動態(tài)規(guī)劃的思維導(dǎo)圖
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

背包九講
https://blog.csdn.net/stack_queue/article/details/53544109