導(dǎo)言

動(dòng)態(tài)規(guī)劃問題一直是算法面試當(dāng)中的重點(diǎn)和難點(diǎn)，并且動(dòng)態(tài)規(guī)劃這種通過空間換取時(shí)間的算法思想在實(shí)際的工作中也會(huì)被頻繁用到，這篇文章的目的主要是解釋清楚
什么是動(dòng)態(tài)規(guī)劃，還有就是面對(duì)一道動(dòng)態(tài)規(guī)劃問題，一般的 思考步驟 以及其中的注意事項(xiàng)等等，最后通過幾道題目將理論和實(shí)踐結(jié)合。

什么是動(dòng)態(tài)規(guī)劃

如果你還沒有聽說過動(dòng)態(tài)規(guī)劃，或者僅僅只有耳聞，或許你可以看看 Quora 上面的這個(gè) 回答。
How to explain dynamic
用一句話解釋動(dòng)態(tài)規(guī)劃就是 “記住你之前做過的事”，如果更準(zhǔn)確些，其實(shí)是 “記住你之前得到的答案”。

我舉個(gè)大家工作中經(jīng)常遇到的例子。

在軟件開發(fā)中，大家經(jīng)常會(huì)遇到一些系統(tǒng)配置的問題，配置不對(duì)，系統(tǒng)就會(huì)報(bào)錯(cuò)，這個(gè)時(shí)候一般都會(huì)去 Google 或者是查閱相關(guān)的文檔，花了一定的時(shí)間將配置修改好。

過了一段時(shí)間，去到另一個(gè)系統(tǒng)，遇到類似的問題，這個(gè)時(shí)候已經(jīng)記不清之前修改過的配置文件長什么樣，這個(gè)時(shí)候有兩種方案，一種方案還是去 Google
或者查閱文檔，另一種方案是借鑒之前修改過的配置，第一種做法其實(shí)是萬金油，因?yàn)槟阌龅降娜魏螁栴}其實(shí)都可以去
Google，去查閱相關(guān)文件找答案，但是這會(huì)花費(fèi)一定的時(shí)間，相比之下，第二種方案肯定會(huì)更加地節(jié)約時(shí)間，但是這個(gè)方案是有條件的，條件如下：

* 之前的問題和當(dāng)前的問題有著關(guān)聯(lián)性，換句話說，之前問題得到的答案可以幫助解決當(dāng)前問題
* 需要記錄之前問題的答案
當(dāng)然在這個(gè)例子中，可以看到的是，上面這兩個(gè)條件均滿足，大可去到之前配置過的文件中，將配置拷貝過來，然后做些細(xì)微的調(diào)整即可解決當(dāng)前問題，節(jié)約了大量的時(shí)間。

不知道你是否從這些描述中發(fā)現(xiàn)，對(duì)于一個(gè)動(dòng)態(tài)規(guī)劃問題，我們只需要從兩個(gè)方面考慮，那就是 找出問題之間的聯(lián)系，以及 記錄答案
，這里的難點(diǎn)其實(shí)是找出問題之間的聯(lián)系，記錄答案只是順帶的事情，利用一些簡單的數(shù)據(jù)結(jié)構(gòu)就可以做到。

概念

上面的解釋如果大家可以理解的話，接

??動(dòng)態(tài)規(guī)劃算法是通過拆分問題，定義問題狀態(tài)和狀態(tài)之間的關(guān)系，使得問題能夠以遞推（或者說分治）的方式去解決。它的幾個(gè)重要概念如下所述。

??階段：對(duì)于一個(gè)完整的問題過程，適當(dāng)?shù)那蟹譃槿舾蓚€(gè)相互聯(lián)系的子問題，每次在求解一個(gè)子問題，則對(duì)應(yīng)一個(gè)階段，整個(gè)問題的求解轉(zhuǎn)化為按照階段次序去求解。

??狀態(tài)：狀態(tài)表示每個(gè)階段開始時(shí)所處的客觀條件，即在求解子問題時(shí)的已知條件。狀態(tài)描述了研究的問題過程中的狀況。

??決策：決策表示當(dāng)求解過程處于某一階段的某一狀態(tài)時(shí)，可以根據(jù)當(dāng)前條件作出不同的選擇，從而確定下一個(gè)階段的狀態(tài)，這種選擇稱為決策。

??策略：由所有階段的決策組成的決策序列稱為全過程策略，簡稱策略。

??最優(yōu)策略：在所有的策略中，找到代價(jià)最小，性能最優(yōu)的策略，此策略稱為最優(yōu)策略。

??狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定兩個(gè)相鄰階段狀態(tài)的演變過程，描述了狀態(tài)之間是如何演變的。

思考動(dòng)態(tài)規(guī)劃問題的四個(gè)步驟

一般解決動(dòng)態(tài)規(guī)劃問題，分為四個(gè)步驟，分別是

* 問題拆解，找到問題之間的具體聯(lián)系
* 狀態(tài)定義
* 遞推方程推導(dǎo)
* 實(shí)現(xiàn)
這里面的重點(diǎn)其實(shí)是前兩個(gè)，如果前兩個(gè)步驟順利完成，后面的遞推方程推導(dǎo)和代碼實(shí)現(xiàn)會(huì)變得非常簡單。

這里還是拿 Quora 上面的例子來講解，“1+1+1+1+1+1+1+1” 得出答案是 8，那么如何快速計(jì)算 “1+
1+1+1+1+1+1+1+1”，我們首先可以對(duì)這個(gè)大的問題進(jìn)行拆解，這里我說的大問題是 9 個(gè) 1 相加，這個(gè)問題可以拆解成 1 + “8 個(gè) 1
相加的答案”，8 個(gè) 1 相加繼續(xù)拆，可以拆解成 1 + “7 個(gè) 1 相加的答案”，… 1 + “0 個(gè) 1 相加的答案”，到這里，第一個(gè)步驟 已經(jīng)完成。

狀態(tài)定義
其實(shí)是需要思考在解決一個(gè)問題的時(shí)候我們做了什么事情，然后得出了什么樣的答案，對(duì)于這個(gè)問題，當(dāng)前問題的答案就是當(dāng)前的狀態(tài)，基于上面的問題拆解，你可以發(fā)現(xiàn)兩個(gè)相鄰的問題的聯(lián)系其實(shí)是
后一個(gè)問題的答案 = 前一個(gè)問題的答案 + 1，這里，狀態(tài)的每次變化就是 +1。

定義好了狀態(tài)，遞推方程就變得非常簡單，就是 dp[i] = dp[i - 1] + 1，這里的 dp[i] 記錄的是當(dāng)前問題的答案，也就是當(dāng)前的狀態(tài)，
dp[i - 1] 記錄的是之前相鄰的問題的答案，也就是之前的狀態(tài)，它們之間通過 +1 來實(shí)現(xiàn)狀態(tài)的變更。

最后一步就是實(shí)現(xiàn)了，有了狀態(tài)表示和遞推方程，實(shí)現(xiàn)這一步上需要重點(diǎn)考慮的其實(shí)是初始化，就是用什么樣的數(shù)據(jù)結(jié)構(gòu)，根據(jù)問題的要求需要做那些初始值的設(shè)定。
public?int?dpExample(int?n)?{
????int[]?dp?=?new?int[n?+?1];??//?多開一位用來存放?0?個(gè)?1?相加的結(jié)果

????dp[0]?=?0;??????//?0?個(gè)?1?相加等于?0

????for?(int?i?=?1;?i?<=?n;?++i)?{
????????dp[i]?=?dp[i?-?1]?+?1;
????}

????return?dp[n];
}


你可以看到，動(dòng)態(tài)規(guī)劃這四個(gè)步驟其實(shí)是相互遞進(jìn)的，狀態(tài)的定義離不開問題的拆解，遞推方程的推導(dǎo)離不開狀態(tài)的定義，最后的實(shí)現(xiàn)代碼的核心其實(shí)就是遞推方程，這中間如果有一個(gè)步驟卡殼了則會(huì)導(dǎo)致問題無法解決，當(dāng)問題的復(fù)雜程度增加的時(shí)候，這里面的思維復(fù)雜程度會(huì)上升。

接下來我們?cè)賮砜纯?LeetCode 上面的幾道題目，通過題目再來走一下這些個(gè)分析步驟。

題目實(shí)戰(zhàn)

爬樓梯

但凡涉及到動(dòng)態(tài)規(guī)劃的題目都離不開一道例題：爬樓梯（LeetCode 第 70 號(hào)問題）。

題目描述

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

示例 1：
輸入：?2
輸出：?2
解釋：?有兩種方法可以爬到樓頂。

1.?1?階?+?1?階
2.?2?階

示例 2：
輸入：?3
輸出：?3
解釋：?有三種方法可以爬到樓頂。

1.?1?階?+?1?階?+?1?階
2.?1?階?+?2?階
3.?2?階?+?1?階

題目解析

爬樓梯，可以爬一步也可以爬兩步，問有多少種不同的方式到達(dá)終點(diǎn)，我們按照上面提到的四個(gè)步驟進(jìn)行分析：

*
問題拆解：

我們到達(dá)第 n 個(gè)樓梯可以從第 n - 1 個(gè)樓梯和第 n - 2 個(gè)樓梯到達(dá)，因此第 n 個(gè)問題可以拆解成第 n - 1 個(gè)問題和第 n - 2
個(gè)問題，第 n - 1 個(gè)問題和第 n - 2 個(gè)問題又可以繼續(xù)往下拆，直到第 0 個(gè)問題，也就是第 0 個(gè)樓梯 (起點(diǎn))

*
狀態(tài)定義

“問題拆解” 中已經(jīng)提到了，第 n 個(gè)樓梯會(huì)和第 n - 1 和第 n - 2 個(gè)樓梯有關(guān)聯(lián)，那么具體的聯(lián)系是什么呢？你可以這樣思考，第 n - 1
個(gè)問題里面的答案其實(shí)是從起點(diǎn)到達(dá)第 n - 1 個(gè)樓梯的路徑總數(shù)，n - 2 同理，從第 n - 1 個(gè)樓梯可以到達(dá)第 n 個(gè)樓梯，從第 n - 2
也可以，并且路徑?jīng)]有重復(fù)，因此我們可以把第 i 個(gè)狀態(tài)定義為 “從起點(diǎn)到達(dá)第 i 個(gè)樓梯的路徑總數(shù)”，狀態(tài)之間的聯(lián)系其實(shí)是相加的關(guān)系。

*
遞推方程

“狀態(tài)定義” 中我們已經(jīng)定義好了狀態(tài)，也知道第 i 個(gè)狀態(tài)可以由第 i - 1 個(gè)狀態(tài)和第 i - 2 個(gè)狀態(tài)通過相加得到，因此遞推方程就出來了 dp[i]
= dp[i - 1] + dp[i - 2]

*
實(shí)現(xiàn)

你其實(shí)可以從遞推方程看到，我們需要有一個(gè)初始值來方便我們計(jì)算，起始位置不需要移動(dòng) dp[0] = 0，第 1 層樓梯只能從起始位置到達(dá)，因此 dp[1] =
1，第 2 層樓梯可以從起始位置和第 1 層樓梯到達(dá)，因此 dp[2] = 2，有了這些初始值，后面就可以通過這幾個(gè)初始值進(jìn)行遞推得到。

參考代碼
public?int?climbStairs(int?n)?{
????if?(n?==?1)?{
????????return?1;
????}

????int[]?dp?=?new?int[n?+?1];??//?多開一位，考慮起始位置

????dp[0]?=?0;?dp[1]?=?1;?dp[2]?=?2;
????for?(int?i?=?3;?i?<=?n;?++i)?{
????????dp[i]?=?dp[i?-?1]?+?dp[i?-?2];
????}

????return?dp[n];
}

三角形最小路徑和

LeetCode 第 120 號(hào)問題：三角形最小路徑和。

題目描述

給定一個(gè)三角形，找出自頂向下的最小路徑和。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。

例如，給定三角形：
[
?????[2],
????[3,4],
???[6,5,7],
??[4,1,8,3]
]

自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

說明：

如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個(gè)問題，那么你的算法會(huì)很加分。

題目解析

給定一個(gè)三角形數(shù)組，需要求出從上到下的最小路徑和，也和之前一樣，按照四個(gè)步驟來分析：

*
問題拆解：

這里的總問題是求出最小的路徑和，路徑是這里的分析重點(diǎn)，路徑是由一個(gè)個(gè)元素組成的，和之前爬樓梯那道題目類似，[i][j]
位置的元素，經(jīng)過這個(gè)元素的路徑肯定也會(huì)經(jīng)過[i - 1][j] 或者 [i - 1][j - 1]
，因此經(jīng)過一個(gè)元素的路徑和可以通過這個(gè)元素上面的一個(gè)或者兩個(gè)元素的路徑和得到。

*
狀態(tài)定義


狀態(tài)的定義一般會(huì)和問題需要求解的答案聯(lián)系在一起，這里其實(shí)有兩種方式，一種是考慮路徑從上到下，另外一種是考慮路徑從下到上，因?yàn)樵氐闹凳遣蛔兊?，所以路徑的方向不同也不?huì)影響最后求得的路徑和，如果是從上到下，你會(huì)發(fā)現(xiàn)，在考慮下面元素的時(shí)候，起始元素的路徑只會(huì)從
[i - 1][j] 獲得，每行當(dāng)中的最后一個(gè)元素的路徑只會(huì)從 [i - 1][j - 1]
獲得，中間二者都可，這樣不太好實(shí)現(xiàn)，因此這里考慮從下到上的方式，狀態(tài)的定義就變成了 “最后一行元素到當(dāng)前元素的最小路徑和”，對(duì)于 [0][0]
這個(gè)元素來說，最后狀態(tài)表示的就是我們的最終答案。

*
遞推方程

“狀態(tài)定義” 中我們已經(jīng)定義好了狀態(tài)，遞推方程就出來了
dp[i][j]?=?Math.min(dp[i?+?1][j],?dp[i?+?1][j?+?1])?+?triangle[i][j]

*
實(shí)現(xiàn)

這里初始化時(shí)，我們需要將最后一行的元素填入狀態(tài)數(shù)組中，然后就是按照前面分析的策略，從下到上計(jì)算即可

參考代碼
public?int?minimumTotal(List<List<Integer>>?triangle)?{
????int?n?=?triangle.size();

????int[][]?dp?=?new?int[n][n];

????List<Integer>?lastRow?=?triangle.get(n?-?1);

????for?(int?i?=?0;?i?<?n;?++i)?{
????????dp[n?-?1][i]?=?lastRow.get(i);
????}

????for?(int?i?=?n?-?2;?i?>=?0;?--i)?{
????????List<Integer>?row?=?triangle.get(i);
????????for?(int?j?=?0;?j?<?i?+?1;?++j)?{
????????????dp[i][j]?=?Math.min(dp[i?+?1][j],?dp[i?+?1][j?+?1])?+?row.get(j);
????????}
????}

????return?dp[0][0];
}

最大子序和

LeetCode 第 53 號(hào)問題：最大子序和。

題目描述

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例:
輸入:?[-2,1,-3,4,-1,2,1,-5,4],
輸出:?6
解釋:?連續(xù)子數(shù)組?[4,-1,2,1]?的和最大，為?6。

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

題目解析


求最大子數(shù)組和，非常經(jīng)典的一道題目，這道題目有很多種不同的做法，而且很多算法思想都可以在這道題目上面體現(xiàn)出來，比如動(dòng)態(tài)規(guī)劃、貪心、分治，還有一些技巧性的東西，比如前綴和數(shù)組，這里還是使用動(dòng)態(tài)規(guī)劃的思想來解題，套路還是之前的四步驟：

*
問題拆解：


問題的核心是子數(shù)組，子數(shù)組可以看作是一段區(qū)間，因此可以由起始點(diǎn)和終止點(diǎn)確定一個(gè)子數(shù)組，兩個(gè)點(diǎn)中，我們先確定一個(gè)點(diǎn)，然后去找另一個(gè)點(diǎn)，比如說，如果我們確定一個(gè)子數(shù)組的截止元素在
i 這個(gè)位置，這個(gè)時(shí)候我們需要思考的問題是 “以 i 結(jié)尾的所有子數(shù)組中，和最大的是多少？”，然后我們?nèi)ピ囍鸾?，這里其實(shí)只有兩種情況：

*
i 這個(gè)位置的元素自成一個(gè)子數(shù)組

*
i 位置的元素的值 + 以 i - 1 結(jié)尾的所有子數(shù)組中的子數(shù)組和最大的值

你可以看到，我們把第 i 個(gè)問題拆成了第 i - 1 個(gè)問題，之間的聯(lián)系也變得清晰

*
狀態(tài)定義

通過上面的分析，其實(shí)狀態(tài)已經(jīng)有了，dp[i] 就是 “以 i 結(jié)尾的所有子數(shù)組的最大值”

*
遞推方程

拆解問題的時(shí)候也提到了，有兩種情況，即當(dāng)前元素自成一個(gè)子數(shù)組，另外可以考慮前一個(gè)狀態(tài)的答案，于是就有了
dp[i]?=?Math.max(dp[i?-?1]?+?array[i],?array[i])

化簡一下就成了：
dp[i]?=?Math.max(dp[i?-?1],?0)?+?array[i]

*
實(shí)現(xiàn)

題目要求子數(shù)組不能為空，因此一開始需要初始化，也就是 dp[0] = array[0]
，保證最后答案的可靠性，另外我們需要用一個(gè)變量記錄最后的答案，因?yàn)樽訑?shù)組有可能以數(shù)組中任意一個(gè)元素結(jié)尾

參考代碼
public?int?maxSubArray(int[]?nums)?{
????if?(nums?==?null?||?nums.length?==?0)?{
????????return?0;
????}

????int?n?=?nums.length;

????int[]?dp?=?new?int[n];

????dp[0]?=?nums[0];

????int?result?=?dp[0];

????for?(int?i?=?1;?i?<?n;?++i)?{
????????dp[i]?=?Math.max(dp[i?-?1],?0)?+?nums[i];
????????result?=?Math.max(result,?dp[i]);
????}

????return?result;
}

總結(jié)

通過這幾個(gè)簡單的例子，相信你不難發(fā)現(xiàn)，解動(dòng)態(tài)規(guī)劃題目其實(shí)就是拆解問題，定義狀態(tài)的過程，嚴(yán)格說來，動(dòng)態(tài)規(guī)劃并不是一個(gè)具體的算法，而是凌駕于算法之上的一種 思想
。


這種思想強(qiáng)調(diào)的是從局部最優(yōu)解通過一定的策略推得全局最優(yōu)解，從子問題的答案一步步推出整個(gè)問題的答案，并且利用空間換取時(shí)間。從很多算法之中你都可以看到動(dòng)態(tài)規(guī)劃的影子，所以，還是那句話
技術(shù)都是相通的，找到背后的本質(zhì)思想是關(guān)鍵。

公眾號(hào)：五分鐘學(xué)算法（ID：CXYxiaowu）
博客：www.cxyxiaowu.com（目前更新了 500 篇算法文章，歡迎訪問學(xué)習(xí)）
知乎：程序員吳師兄
一個(gè)正在學(xué)習(xí)算法的人，致力于將算法講清楚?！

?

• ? 上一篇： MySQL中SQL優(yōu)化的常用方法
• ? 下一篇：在Web中獲取MAC地址