一張腦圖帶你看動(dòng)態(tài)劃算法之美
前言
算法中有個(gè)專題，動(dòng)態(tài)規(guī)劃，它十分的重要，大廠面試中或多或少有所涉及，來網(wǎng)易之前，刷了部分dp，這次正好再次梳理一遍，希望對你們有一點(diǎn)點(diǎn)幫助。
如果你已經(jīng)懂了dp思路，或者已經(jīng)掌握了常見的dp解法，可以直接跳過。
如果你還不了解，或者知道動(dòng)態(tài)規(guī)劃，但是還沒有開始刷題的話，可能這篇文章適合你。
公眾號「全棧前端精選」，回復(fù)dp，即可獲取腦圖。
腦圖?
什么是動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃（Dynamic Programming），因此常用 DP 指代動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃，首先我們得清楚，它的概念是啥，它能解決什么問題，維基百科對它的解釋?
?動(dòng)態(tài)規(guī)劃在尋找有很多重疊子問題的情況的最佳解時(shí)有效。它將問題重新組合成子問題，為了避免多次解決這些子問題，它們的結(jié)果都逐漸被計(jì)算并被儲(chǔ)存，從簡單的問題直到整個(gè)問題都被解決。因此，動(dòng)態(tài)規(guī)劃儲(chǔ)存遞歸時(shí)的結(jié)果，因而不會(huì)在解決同樣的問題時(shí)花費(fèi)時(shí)間。
動(dòng)態(tài)規(guī)劃只能應(yīng)用于有最佳子結(jié)構(gòu)的問題。最佳子結(jié)構(gòu)的意思是局部最佳解能決定全域最佳解（對有些問題這個(gè)要求并不能完全滿足，故有時(shí)需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。
?
我稍微總結(jié)一下?
將一個(gè)大的問題拆分成一個(gè)個(gè)子問題，我們把它稱之為子結(jié)構(gòu)。 每個(gè)最優(yōu)解，也就是「最優(yōu)值」均由[這些小規(guī)模子問題]推到而來。 更重要的就是利用 歷史記錄，來避免我們重復(fù)的計(jì)算。
什么是重復(fù)計(jì)算，那怎么樣可以利用歷史記錄來減少我們不必要的運(yùn)算呢?
我們拿「斐波那契數(shù)列」這題來看?
如果我們按照這個(gè)遞歸的寫法來看，那么它的過程如下?
它會(huì)多次計(jì)算結(jié)果，這個(gè)符合動(dòng)態(tài)規(guī)劃的點(diǎn)，**動(dòng)態(tài)規(guī)劃在尋找有很多重疊子問題的情況的最佳解時(shí)有效。**而且對于這個(gè)問題而言，它可以繼續(xù)去拆分，變成更小的子問題去解決，它也符合動(dòng)態(tài)規(guī)劃的預(yù)期。
那么這里只是舉個(gè)例子，后續(xù)會(huì)將做題思路?
動(dòng)態(tài)規(guī)劃解題三大步驟
對于初學(xué)者而言，需要短時(shí)間就掌握的話，我覺得挺難的，所以這里我推薦大家可以看看「經(jīng)典的動(dòng)態(tài)規(guī)劃」?背包九講，點(diǎn)這里，看完它，或許對你有點(diǎn)幫助吧。
解題思路，三大步驟?
「狀態(tài)定義」 「列出狀態(tài)轉(zhuǎn)移方程」 「初始化狀態(tài)」
「狀態(tài)定義」
我們需要借助數(shù)組來保存之前計(jì)算的結(jié)果，所以一般采用的就是數(shù)組來維護(hù)我們的結(jié)果，一般dp數(shù)組。 dp數(shù)組的含義一定要明確，也就是說，dp[i]表達(dá)是啥意思，舉個(gè)例子，dp[i]表達(dá)到達(dá)第i個(gè)階梯時(shí)的方案數(shù)。
「列出狀態(tài)轉(zhuǎn)移方程」
通俗易懂的話，找出數(shù)組間關(guān)系式，這個(gè)時(shí)解決動(dòng)態(tài)規(guī)范問題中，最難也是最重要的一步。 通常情況而言，dp[i]個(gè)狀態(tài)的轉(zhuǎn)移方程，跟dp[i-1] 與 dp[i-2] 之間存在某種聯(lián)系。
舉個(gè)例子，后續(xù)爬梯子的題目中，狀態(tài)轉(zhuǎn)移方程?
dp[i]?=?dp[i-1]?+?dp[i-2]
首先dp[i] 表示的就到第i個(gè)階梯的方案數(shù) 那么爬到第i階梯，有兩種情況? 從第i-1階梯再爬1階就到第i階 從第i-2階梯再爬2階就到第i階 那么它的狀態(tài)方程轉(zhuǎn)移就是上面的式子
「初始化狀態(tài)」
我們會(huì)發(fā)現(xiàn)，dp數(shù)組的第n項(xiàng)結(jié)果，是由狀態(tài)轉(zhuǎn)移方程求解而言的，所以我們需要的是第n-1項(xiàng)，n-2項(xiàng)，或者n-3項(xiàng)的值。 這個(gè)時(shí)候，我們就需要初始話dp數(shù)組的值，一般而言，比如 dp[1],dp[2],dp[1][1],dp[1][2]。
從上面的場景，爬樓梯來說，我們需要初始話哪一項(xiàng)dp數(shù)組呢，當(dāng)我們依次迭代到dp[3] = dp[1] + dp[2]，接下來就不再需要去分解了。
這個(gè)時(shí)候，我們實(shí)際意義而言，就需要我們?nèi)コ跏蓟?，dp[1]和dp[2]數(shù)組。
動(dòng)態(tài)規(guī)劃分類
這么久以來，隨著動(dòng)態(tài)規(guī)劃這種算法思路被很多牛人去探索，動(dòng)態(tài)規(guī)劃這類問題，被分為了很多種，參考網(wǎng)上的資料，列舉了幾個(gè)常見的dp，我們接下來看看吧。
我的經(jīng)驗(yàn)之談，按照不同dp專題來刷，效果很明顯，當(dāng)然了，具體看你自己掌握情況，以及刷題速度了。
背包dp
這算是狀態(tài)規(guī)劃中比較經(jīng)典的題目了，對于理解dp的話，我個(gè)人覺得很有幫助，也是我入門dp最開始看的專題?
dd大牛的《背包九講》 ?，可以看看這篇，這里就不展開了。
這里推薦幾道題?
分割等和子集- 01背包 目標(biāo)和 - 01背包-求方案數(shù) 零錢兌換 - 完全背包 零錢兌換- II (完全背包-求方案數(shù)) 一和零 - ?(二維費(fèi)用背包)
線性dp
顧名思義，線性DP就是在一條線上進(jìn)行DP。 或者我的理解是，就是在線性空間上的遞推。
這里推薦幾道題?
最長上升子序列
三角形最小路徑和
最長公共子序列
最大子序和
俄羅斯套娃信封問題
區(qū)間dp
顧名思義，在一段區(qū)間上dp，類似于
dp[l][r]構(gòu)成的，我們也是將大問題拆分成小問題來處理，這里就是拆分成小區(qū)間來處理。然后對小區(qū)間處理后，再回溯的求出大區(qū)間的值。
主要的方法有兩種，記憶化搜索和遞推。
這里推薦幾道題?
最長回文子序列 統(tǒng)計(jì)不同回文子序列 多邊形三角剖分的最低得分 戳氣球 奇怪的打印機(jī)
樹形dp
準(zhǔn)確的來說，樹形dp準(zhǔn)確的說是一種dp的思想，將dp建立在樹狀結(jié)構(gòu)的基礎(chǔ)上。 你可以理解成，在一顆樹上定義dp方程式，完成相應(yīng)的操作。
這里推薦幾道題?
打家劫舍 III 「時(shí)態(tài)同步」 「選課」 二叉樹中的最大路徑和 二叉樹的直徑 「戰(zhàn)略游戲」
數(shù)位dp
數(shù)位dp是一種計(jì)數(shù)用的dp，一般就是要統(tǒng)計(jì)一個(gè)區(qū)間[le,ri]內(nèi)滿足一些條件數(shù)的個(gè)數(shù)。 所謂數(shù)位dp，字面意思就是在數(shù)位上進(jìn)行dp咯。 數(shù)位還算是比較好聽的名字，數(shù)位的含義：一個(gè)數(shù)有個(gè)位、十位、百位、千位......數(shù)的每一位就是數(shù)位啦！
這里推薦幾道題?
數(shù)字 1 的個(gè)數(shù) 最大為 N 的數(shù)字組合 可被 K 整除的最小整數(shù)
我印象中，這個(gè)是模板，自己寫很難，但是這是個(gè)板子題，哈哈哈，打過Acm都知道，這里就不展開了。
「狀態(tài)壓縮DP」 「計(jì)數(shù)型DP」 「遞推型DP」 「概率型DP」 「博弈型DP」，嗯太多了，只當(dāng)是拋磚引玉吧。
3個(gè)例子
接下來，我們就以三題為例子，來強(qiáng)化我們解題思路的三大步驟吧?
爬樓梯?
?鏈接：爬樓梯
?
假設(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?階
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/climbing-stairs 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
「我們按照解題思路走一遍?」
「第一步：狀態(tài)定義」
dp[i] 表示的含義:到第i階方案數(shù)
「第二步：確定狀態(tài)轉(zhuǎn)移方程」
根據(jù)實(shí)際的情況，我們很容易想到?
到第i階梯有兩種方式 第一種, 從i-1向上走一步即可 第二中，從i-2向上走二步即可 所以 dp[i] = dp[i-1] + dp[i-2]
「第三步,初始化狀態(tài)，dp數(shù)組」
dp[1]?=?1,dp[2]?=?2
按照這個(gè)三步走的話，我們就可以寫出完整的解題代碼
代碼?
代碼點(diǎn)這里??
打家劫???
?鏈接：打家劫舍 II
?
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都圍成一圈，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。
示例 1:
輸入:?[2,3,2]
輸出:?3
解釋:?你不能先偷竊 1 號房屋（金額?= 2），然后偷竊 3 號房屋（金額?= 2）, 因?yàn)樗麄兪窍噜彽摹?br>示例 2:
輸入:?[1,2,3,1]
輸出:?4
解釋:?你可以先偷竊 1 號房屋（金額?= 1），然后偷竊 3 號房屋（金額?= 3）。
?????偷竊到的最高金額?= 1 + 3 = 4 。
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/house-robber-ii 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
「我們按照解題思路走一遍?」
「第一步：狀態(tài)定義」
//?這里就利用二維狀態(tài),既然可以選擇偷或者是不偷
//?dp[i][0]?表示不偷當(dāng)前第i個(gè)房間,獲取最高金幣數(shù)
//?dp[i][1]?表示的是偷第i房間,獲取最高金幣數(shù)
「第二步：確定狀態(tài)轉(zhuǎn)移方程」
//?第i個(gè)房間偷的話,dp[i][1]?=?nums[i]?+?dp[i-1][0]
//?第i個(gè)房間不偷的話,?dp[i][0]?=?Math.max(dp[i-1][0],dp[i-1][1])
「第三步,初始化狀態(tài)，dp數(shù)組」
//?dp[0][0]?=?0
//?dp[0][1]?=?nums[0]
但是這個(gè)題目的難點(diǎn)在于?
第一個(gè)房子跟最后一個(gè)房子是挨著的，意味著我們需要做些改變，這個(gè)我也是在提示下完成的，寫法很巧妙，我們具體看下代碼下?
按照這個(gè)三步走的話，我們就可以寫出完整的解題代碼?
代碼點(diǎn)這里??
買賣股票的最佳時(shí)機(jī) IV???
給你一個(gè)二叉樹，請你返回其按 「層序遍歷」 得到的節(jié)點(diǎn)值。（即逐層地，從左到右訪問所有節(jié)點(diǎn)）。
?鏈接：買賣股票的最佳時(shí)機(jī) IV
?
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你最多可以完成 k 筆交易。
注意: 你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入:?[2,4,1],?k?=?2
輸出:?2
解釋:?在第 1 天?(股票價(jià)格?= 2)?的時(shí)候買入，在第 2 天?(股票價(jià)格?= 4)?的時(shí)候賣出，這筆交易所能獲得利潤?= 4-2 = 2 。
示例 2:
輸入:?[3,2,6,5,0,3],?k?=?2
輸出:?7
解釋:?在第 2 天?(股票價(jià)格?= 2)?的時(shí)候買入，在第 3 天?(股票價(jià)格?= 6)?的時(shí)候賣出, 這筆交易所能獲得利潤?= 6-2 = 4 。
?????隨后，在第 5 天?(股票價(jià)格?=?0)?的時(shí)候買入，在第 6 天?(股票價(jià)格?= 3)?的時(shí)候賣出, 這筆交易所能獲得利潤?= 3-0?= 3 。
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
「第一步：狀態(tài)定義」
?//?可以定義如下
?//?dp[i][j][0]?表示第i天交易了j次時(shí)賣出后的累計(jì)最大利潤
?//??dp[i][j][1]?表示第i天交易了j次時(shí)買入后的累計(jì)最大利潤
「第二步：確定狀態(tài)轉(zhuǎn)移方程」
??//?第二步：確定狀態(tài)轉(zhuǎn)移方程
?//?dp[i][j][0]?當(dāng)?shù)趇天不持股的話，我們需要確定昨天是否持有股票
?//?dp[i][j][0]?=?max(dp[i?-?1][j][0],?dp[i?-?1][j][1]?+?prices[i])
?//?dp[i][j][1]?同樣的第i天,我們需要去確定昨天是否持有股票
?//?dp[i][j][1]?=?max(dp[i?-?1][j][1],?dp[i?-?1][j?-?1][0]?-?prices[i])
「第三步,初始化狀態(tài)，dp數(shù)組」
//?所有不持股的狀態(tài)值初始化的時(shí)候?yàn)?0。所有持股的狀態(tài)值都設(shè)置為一個(gè)很大的負(fù)數(shù)（至少應(yīng)該是最大的股價(jià)的負(fù)數(shù)?- 1），表示未知。
//?dp[0][j][0]?=?0;
//?dp[0][j][1]?=?-prices[i];
但是這個(gè)題目的難點(diǎn)在于?
當(dāng)k大于len/2的時(shí)候，我們需要做一個(gè)處理，或者說，我們需要利用狀態(tài)壓縮，好難，我們看看該如何寫吧?
代碼點(diǎn)這里??
進(jìn)階題目匯總
以下是我收集的部分題目，希望對你們有幫助。
簡單
爬樓梯 打家劫舍 使用最小花費(fèi)爬樓梯 連續(xù)數(shù)列 三步問題
中等
打家劫舍 II 最佳買賣股票時(shí)機(jī)含冷凍期 打家劫舍 III 不同路徑 不同路徑 II 最長上升子序列
困難
買賣股票的最佳時(shí)機(jī) III 買賣股票的最佳時(shí)機(jī) IV 青蛙過河 單詞拆分 II 最大子矩陣
參考
告別動(dòng)態(tài)規(guī)劃，連刷 40 道題，我總結(jié)了這些套路 如何理解動(dòng)態(tài)規(guī)劃？ 動(dòng)態(tài)規(guī)劃之背包問題系列 dd大牛的《背包九講》 [力扣] DP問題分類匯總