1. 從“最長上升子序列”說起為什么動(dòng)態(tài)規(guī)劃是繞不開的坎如果你刷過一些算法題或者正準(zhǔn)備踏入這個(gè)領(lǐng)域大概率會(huì)碰到“最長上升子序列”Longest Increasing Subsequence, LIS這個(gè)問題。它太經(jīng)典了經(jīng)典到幾乎成了動(dòng)態(tài)規(guī)劃Dynamic Programming, DP的“名片”。題目描述很簡單給定一個(gè)無序的整數(shù)序列找到其中最長的、嚴(yán)格遞增的子序列的長度。比如序列[10, 9, 2, 5, 3, 7, 101, 18]最長的上升子序列之一是[2, 3, 7, 101]長度為4。新手看到這個(gè)問題第一反應(yīng)可能是暴力枚舉所有子序列然后檢查是否遞增。但稍微算一下就知道一個(gè)長度為n的序列子序列總數(shù)是2^n這顯然是指數(shù)級(jí)的災(zāi)難。于是你開始尋找更優(yōu)解然后就會(huì)在各種攻略、題解里反復(fù)看到一個(gè)詞動(dòng)態(tài)規(guī)劃。很多教程會(huì)直接甩給你一個(gè)狀態(tài)定義dp[i]表示以第i個(gè)元素結(jié)尾的最長上升子序列長度然后給出狀態(tài)轉(zhuǎn)移方程dp[i] max(dp[j]) 1 (其中 j i 且 nums[j] nums[i])。背下來似乎也能解題。但問題來了這個(gè)dp[i]是怎么想出來的為什么是“以第i個(gè)元素結(jié)尾”為什么狀態(tài)轉(zhuǎn)移要去看前面所有的j這背后隱藏的動(dòng)態(tài)規(guī)劃核心思想——子問題分析才是真正需要啃下的硬骨頭。很多人學(xué)動(dòng)態(tài)規(guī)劃感到吃力就是因?yàn)樘^了“定義子問題”這個(gè)最關(guān)鍵的思考過程直接去記憶和套用模板。今天我們就以“最長上升子序列”這個(gè)經(jīng)典案例為引子深入Level 2的層面拆解動(dòng)態(tài)規(guī)劃中“子問題分析”的完整心路歷程。這不是一篇教你背公式的文章而是一次思維過程的慢放讓你看清高手是如何一步步把一個(gè)大問題拆解成可管理、可重復(fù)利用的小問題的。2. 動(dòng)態(tài)規(guī)劃的本質(zhì)不是算法是方法論在深入案例之前我們必須統(tǒng)一思想動(dòng)態(tài)規(guī)劃首先是一種方法論其次才體現(xiàn)為具體的算法實(shí)現(xiàn)。它的核心目標(biāo)是通過巧妙地定義子問題和存儲(chǔ)子問題的解來避免重復(fù)計(jì)算從而高效解決那些具有“重疊子問題”和“最優(yōu)子結(jié)構(gòu)”特性的復(fù)雜問題。2.1 重疊子問題與最優(yōu)子結(jié)構(gòu)兩個(gè)基石這兩個(gè)術(shù)語聽起來很學(xué)術(shù)我們用最直白的方式解釋重疊子問題在解決大問題的過程中你需要反復(fù)解決許多一模一樣的小問題。比如在計(jì)算斐波那契數(shù)列F(5)時(shí)你需要計(jì)算F(4)和F(3)計(jì)算F(4)時(shí)又需要計(jì)算F(3)和F(2)。你看F(3)被計(jì)算了多次。這就是重疊子問題。如果傻傻地用遞歸就會(huì)造成巨大的計(jì)算浪費(fèi)。動(dòng)態(tài)規(guī)劃通過“記筆記”即DP表把算過的F(3)存起來下次直接用。最優(yōu)子結(jié)構(gòu)一個(gè)大問題的最優(yōu)解可以通過其子問題的最優(yōu)解組合得到。這是動(dòng)態(tài)規(guī)劃能夠成立的前提。如果子問題的最優(yōu)解無法構(gòu)成原問題的最優(yōu)解那動(dòng)態(tài)規(guī)劃就無效。例如在“最短路徑”問題中從A到C的最短路徑如果經(jīng)過B那么這條路徑必然由A到B的最短路徑和B到C的最短路徑組成。注意很多問題具有“子結(jié)構(gòu)”但不一定是“最優(yōu)子結(jié)構(gòu)”。比如最長路徑問題就不具有最優(yōu)子結(jié)構(gòu)因?yàn)榫植孔铋L無法保證全局最長。所以拿到問題第一件事是判斷它是否適合用DP而判斷的關(guān)鍵往往始于對(duì)子問題的分析。2.2 子問題分析動(dòng)態(tài)規(guī)劃的靈魂步驟子問題分析就是尋找那個(gè)“牽一發(fā)而動(dòng)全身”的切入點(diǎn)。一個(gè)好的子問題定義應(yīng)該具備以下特點(diǎn)與原問題同構(gòu)子問題應(yīng)該是原問題的一個(gè)縮小版形式相同。邊界清晰存在一個(gè)或多個(gè)顯而易見的、無需計(jì)算就能得出答案的“最小子問題”即初始狀態(tài)。能推導(dǎo)出原問題通過某種規(guī)則可以由子問題的解有效地推導(dǎo)出更大規(guī)模子問題乃至原問題的解。這個(gè)過程沒有固定公式更像是一種藝術(shù)。我們回到“最長上升子序列”問題看看這個(gè)分析過程是如何發(fā)生的。3. 案例深潛最長上升子序列的子問題拆解全記錄假設(shè)我們面對(duì)序列nums [10, 9, 2, 5, 3, 7, 101, 18]。目標(biāo)是求LIS長度。3.1 第一步暴力搜索的視角與啟發(fā)最笨的方法是枚舉所有子序列。當(dāng)我們枚舉時(shí)潛意識(shí)里其實(shí)在做一種決策對(duì)于序列中的每一個(gè)數(shù)在構(gòu)造當(dāng)前子序列時(shí)只有兩種選擇——“選它”或者“不選它”。但這會(huì)形成一棵龐大的二叉決策樹。我們可以換個(gè)角度思考如果我強(qiáng)制規(guī)定找出來的最長上升子序列必須以某個(gè)特定的數(shù)結(jié)尾會(huì)怎么樣比如我必須找一個(gè)以7結(jié)尾的上升子序列。那么這個(gè)子序列的前一個(gè)數(shù)只能是7前面那些比7小的數(shù)2,5,3中的一個(gè)。那么以7結(jié)尾的最長上升子序列的長度就等于“從前面那些比7小的數(shù)里挑一個(gè)結(jié)尾形成最長序列然后接上7”。這個(gè)想法至關(guān)重要它把一個(gè)“全局自由”的問題轉(zhuǎn)化為了一個(gè)“帶約束”的問題。約束就是子序列的結(jié)尾元素固定。3.2 第二步定義狀態(tài)子問題基于上面的啟發(fā)我們自然可以定義一組子問題子問題 dp[i]表示以原序列中第i個(gè)位置下標(biāo)通常從0開始的數(shù)字nums[i]作為結(jié)尾的最長上升子序列的長度。為什么這么定義同構(gòu)性每個(gè)dp[i]本身就是一個(gè)“最長上升子序列”問題只不過定義域縮小到了前綴nums[0...i]且加上了“必須以nums[i]結(jié)尾”的約束。邊界清晰對(duì)于任何一個(gè)位置i最短的、以nums[i]結(jié)尾的上升子序列就是它自己長度為1。所以初始狀態(tài)dp[i] 1對(duì)所有i都成立。目標(biāo)關(guān)聯(lián)原序列的LIS長度必然是以其中某個(gè)數(shù)結(jié)尾的。所以原問題的答案就是所有dp[i]中的最大值即max(dp[0], dp[1], ..., dp[n-1])。3.3 第三步推導(dǎo)狀態(tài)轉(zhuǎn)移方程子問題間的關(guān)系這是動(dòng)態(tài)規(guī)劃最核心的一步也是子問題分析能力的直接體現(xiàn)。我們現(xiàn)在知道了dp[i]的含義那么dp[i]的值應(yīng)該怎么算出來根據(jù)定義dp[i]是以nums[i]結(jié)尾的LIS長度。既然序列必須以nums[i]結(jié)尾那么nums[i]的前一個(gè)數(shù)倒數(shù)第二個(gè)數(shù)是誰它可以是nums[i]之前、任何比nums[i]小的數(shù)nums[j](其中0 j i且nums[j] nums[i])。如果這個(gè)“前一個(gè)數(shù)”是nums[j]那么以nums[i]結(jié)尾的整個(gè)序列就可以看作是在“以nums[j]結(jié)尾的LIS”后面接上nums[i]。因此這種情況下新的序列長度就是dp[j] 1。nums[i]前面可能有多個(gè)符合條件的j多個(gè)比它小的數(shù)我們應(yīng)該選哪個(gè)因?yàn)槲覀円业氖恰白铋L”的所以應(yīng)該選擇能使得dp[j] 1最大的那個(gè)j。如果前面沒有比nums[i]小的數(shù)那nums[i]就只能自己作為一個(gè)序列開頭長度為1也就是我們初始化的值。于是狀態(tài)轉(zhuǎn)移方程就呼之欲出了dp[i] max(1, max{ dp[j] 1 for all j i and nums[j] nums[i] })這個(gè)方程完美詮釋了“最優(yōu)子結(jié)構(gòu)”為了求dp[i]這個(gè)子問題的最優(yōu)解我們需要遍歷所有更小的子問題dp[j]的最優(yōu)解并從中選出最好的一個(gè)來組合。3.4 第四步模擬計(jì)算與填表理論有了我們手動(dòng)模擬一下感受動(dòng)態(tài)規(guī)劃“表格”的填充過程這能極大地加深理解。下標(biāo) inums[i]dp[i] 計(jì)算過程j遍歷 0 到 i-1dp[i] 值解釋以nums[i]結(jié)尾的LIS舉例010前面無數(shù)初始為11[10]19j0: 109不滿足。初始為11[9]22j0:102; j1:92。初始為11[2]35j0:105; j1:95;j2:25, dp[2]12。max(1,2)22[2, 5]43j0,1:不滿足j2:23, dp[2]12j3:53。max(1,2)22[2, 3]57j0,1:不滿足j2:27, dp[2]12j3:57, dp[3]13j4:37, dp[4]13。max(1,2,3,3)33[2, 5, 7] 或 [2, 3, 7]6101遍歷j0到5所有數(shù)都小于101。找到最大的dp[j]是dp[5]3。所以dp[6]3144[2, 5, 7, 101] 或 [2, 3, 7, 101]718遍歷j0到6比18小的數(shù)中最大的dp[j]是dp[5]3對(duì)應(yīng)數(shù)字7。所以dp[7]3144[2, 5, 7, 18] 或 [2, 3, 7, 18]最終所有dp[i]中的最大值是4所以原序列的LIS長度是4。實(shí)操心得手動(dòng)填一兩遍表勝過看十遍代碼。這個(gè)過程能讓你直觀地看到每個(gè)子問題的解是如何依賴于更小的子問題的這是理解動(dòng)態(tài)規(guī)劃不可或缺的一環(huán)。很多人在面試時(shí)卡殼就是因?yàn)橹辉谀X子里想沒有動(dòng)筆把這個(gè)依賴關(guān)系畫清楚。4. 從理論到代碼實(shí)現(xiàn)與優(yōu)化理解了子問題分析和狀態(tài)轉(zhuǎn)移代碼實(shí)現(xiàn)就是水到渠成的事情。4.1 基礎(chǔ)動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)def length_of_lis(nums): if not nums: return 0 n len(nums) # 1. 定義dp數(shù)組初始化所有值為1 dp [1] * n # 2. 外層循環(huán)計(jì)算每一個(gè)dp[i] for i in range(n): # 內(nèi)層循環(huán)遍歷所有可能的“前一個(gè)數(shù)” nums[j] for j in range(i): if nums[j] nums[i]: # 3. 狀態(tài)轉(zhuǎn)移嘗試用dp[j]來更新dp[i] dp[i] max(dp[i], dp[j] 1) # 4. 結(jié)果是dp數(shù)組中的最大值 return max(dp) # 測試 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis(nums)) # 輸出4時(shí)間復(fù)雜度O(n2)因?yàn)橛袃蓪忧短籽h(huán)?？臻g復(fù)雜度O(n)用于存儲(chǔ)dp數(shù)組。4.2 優(yōu)化思路貪心二分查找O(n2)的復(fù)雜度在數(shù)據(jù)量大時(shí)比如n10^5依然不夠看。有沒有更優(yōu)的方法有其核心在于子問題定義的進(jìn)一步優(yōu)化。我們定義一個(gè)新的子問題子問題 tail[k]表示長度為k1的所有上升子序列中結(jié)尾數(shù)字最小的那個(gè)子序列的結(jié)尾數(shù)字。這個(gè)定義非常巧妙。我們維護(hù)一個(gè)數(shù)組tail它的長度就是當(dāng)前找到的最長上升子序列的長度。tail[i]的值代表了在掃描過的數(shù)字中能夠構(gòu)成長度為i1的上升子序列時(shí)所需的最小結(jié)尾數(shù)字。維護(hù)過程遍歷每個(gè)數(shù)字x。在tail數(shù)組中尋找第一個(gè)大于等于x的位置。這個(gè)查找可以用二分法完成因?yàn)閠ail數(shù)組本身是嚴(yán)格遞增的可以證明。如果找到說明存在一個(gè)更長的子序列可以用更小的結(jié)尾數(shù)字x來更新我們用x替換掉那個(gè)位置原來的數(shù)。如果沒找到即x比tail中所有數(shù)都大說明x可以接在當(dāng)前最長的子序列后面形成更長的子序列我們將x追加到tail末尾。這個(gè)過程保證了tail數(shù)組始終是遞增的并且它的最終長度就是LIS的長度。import bisect def length_of_lis_optimized(nums): if not nums: return 0 tail [] for num in nums: # 在tail中二分查找第一個(gè) num 的位置 pos bisect.bisect_left(tail, num) if pos len(tail): # num比所有數(shù)都大延長子序列 tail.append(num) else: # 用更小的num替換掉pos位置的數(shù) tail[pos] num return len(tail) # 測試 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_optimized(nums)) # 輸出4時(shí)間復(fù)雜度O(n log n)遍歷n個(gè)元素每個(gè)元素進(jìn)行一次O(log n)的二分查找?？臻g復(fù)雜度O(n)最壞情況下tail數(shù)組和原數(shù)組等長。注意事項(xiàng)這個(gè)優(yōu)化算法得到的tail數(shù)組其內(nèi)容不一定是一個(gè)真實(shí)的、合法的LIS但它的長度一定是正確的LIS長度。如果需要輸出具體的序列基礎(chǔ)DP方法可以通過記錄“前驅(qū)”節(jié)點(diǎn)來回溯而優(yōu)化方法則不行。這是時(shí)間效率和信息完整性之間的一個(gè)權(quán)衡。5. 舉一反三子問題分析在其他經(jīng)典DP問題中的應(yīng)用掌握了LIS的分析方法我們可以將其應(yīng)用到其他經(jīng)典問題上你會(huì)發(fā)現(xiàn)套路是相通的。5.1 最大子數(shù)組和Kadane算法問題給定一個(gè)整數(shù)數(shù)組找出一個(gè)具有最大和的連續(xù)子數(shù)組。子問題分析暴力搜索枚舉所有子數(shù)組O(n2)。DP思路如果我們定義dp[i]為“以第i個(gè)元素結(jié)尾的最大子數(shù)組和”會(huì)怎么樣那么對(duì)于dp[i]它有兩種選擇要么只包含自己 (nums[i])要么接在以i-1結(jié)尾的最大子數(shù)組后面 (dp[i-1] nums[i])。狀態(tài)轉(zhuǎn)移方程dp[i] max(nums[i], dp[i-1] nums[i])。原問題的答案是max(dp[0], ..., dp[n-1])。這其實(shí)就是Kadane算法的動(dòng)態(tài)規(guī)劃形式空間可以優(yōu)化到O(1)。5.2 不同路徑網(wǎng)格路徑問題問題一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角每次只能向下或向右移動(dòng)一步問到達(dá)右下角有多少條不同路徑。子問題分析定義dp[i][j]為從起點(diǎn)(0,0)走到格子(i,j)的不同路徑數(shù)。如何走到(i,j)要么從上面的格子(i-1,j)走下來要么從左邊的格子(i,j-1)走過來。這兩種方式是互斥且完備的。狀態(tài)轉(zhuǎn)移方程dp[i][j] dp[i-1][j] dp[i][j-1]。邊界條件第一行dp[0][j]和第一列dp[i][0]都只有一種走法直走所以初始化為1。5.3 0-1背包問題問題有N件物品和一個(gè)容量為V的背包。第i件物品的體積是v[i]價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的總體積不超過背包容量且總價(jià)值最大。子問題分析 這是二維子問題的經(jīng)典案例。定義dp[i][c]為考慮前i件物品在背包容量為c的情況下可以裝入的最大價(jià)值。對(duì)于第i件物品我們有兩種選擇不裝那么最大價(jià)值就是考慮前i-1件物品、容量為c時(shí)的最大價(jià)值即dp[i-1][c]。裝前提是能裝下即c v[i]那么最大價(jià)值就是“第i件物品的價(jià)值w[i]”加上“考慮前i-1件物品、剩余容量為c-v[i]時(shí)的最大價(jià)值”即w[i] dp[i-1][c-v[i]]。狀態(tài)轉(zhuǎn)移方程dp[i][c] max(dp[i-1][c], w[i] dp[i-1][c-v[i]])當(dāng)c v[i]時(shí)。邊界條件dp[0][...] 0考慮0件物品價(jià)值為0。6. 動(dòng)態(tài)規(guī)劃解題的通用思維框架與避坑指南根據(jù)上面的案例分析我們可以總結(jié)出一套解決動(dòng)態(tài)規(guī)劃問題的通用思維框架確定狀態(tài)定義子問題這是最難也最關(guān)鍵的一步。問自己問題的哪個(gè)維度在變化通常狀態(tài)參數(shù)對(duì)應(yīng)著問題規(guī)?？s小的維度如序列長度i、背包容量c、坐標(biāo)(i,j)。一個(gè)經(jīng)典技巧是嘗試在問題描述中加上“一定條件下”比如“以...結(jié)尾”、“考慮前...個(gè)”、“在...容量下”。確定狀態(tài)轉(zhuǎn)移方程找出子問題之間的關(guān)系。思考要得到當(dāng)前狀態(tài)需要哪些已經(jīng)計(jì)算出來的子狀態(tài)它們之間如何組合取最大、最小、求和等這一步是數(shù)學(xué)建模。確定初始狀態(tài)邊界條件最小的、不可再分的子問題是什么它們的解通常是顯而易見的如空序列、容量為0、起點(diǎn)位置。確定計(jì)算順序?yàn)榱吮ＷC在計(jì)算一個(gè)狀態(tài)時(shí)它所依賴的子狀態(tài)都已經(jīng)被計(jì)算出來我們需要確定一個(gè)正確的填表順序通常是自底向上從左到右從上到下。代碼實(shí)現(xiàn)與優(yōu)化將上述思路轉(zhuǎn)化為代碼。考慮空間優(yōu)化例如滾動(dòng)數(shù)組有時(shí)也需要考慮時(shí)間優(yōu)化如斜率優(yōu)化、四邊形不等式等高級(jí)技巧。常見問題與排查技巧實(shí)錄問題1狀態(tài)定義想不出來怎么辦技巧從暴力搜索開始思考。暴力搜索的遞歸函數(shù)通常有哪些參數(shù)這些參數(shù)往往就是狀態(tài)定義的維度。例如在遞歸計(jì)算斐波那契數(shù)時(shí)參數(shù)是n在遞歸枚舉子序列時(shí)參數(shù)可能是當(dāng)前索引i和前一個(gè)數(shù)的值prev。prev這個(gè)信息如果很多可以想想能否把它“編碼”到狀態(tài)里或者通過定義方式規(guī)避掉如LIS中定義為“以i結(jié)尾”就自然包含了prev的信息。問題2狀態(tài)轉(zhuǎn)移方程寫錯(cuò)了導(dǎo)致結(jié)果不對(duì)。排查一定要手動(dòng)模擬小規(guī)模數(shù)據(jù)畫出DP表一步步推導(dǎo)。這是最有效的調(diào)試方法。檢查邊界條件i0,j0,c0等是否處理正確。檢查轉(zhuǎn)移條件如背包問題中的容量判斷是否遺漏。問題3遞歸實(shí)現(xiàn)超時(shí)但改成遞推自底向上又很繞。心得優(yōu)先掌握自底向上的遞推寫法填表法。它更符合動(dòng)態(tài)規(guī)劃“利用已計(jì)算子問題”的本意而且通常比遞歸記憶化搜索有更好的常數(shù)性能也更容易進(jìn)行空間優(yōu)化。把遞推過程想象成填滿一個(gè)表格順序很重要。問題4空間復(fù)雜度太高如何優(yōu)化技巧觀察狀態(tài)轉(zhuǎn)移方程。如果dp[i][...]只依賴于dp[i-1][...]即上一行那么通?？梢杂脻L動(dòng)數(shù)組將空間從O(mn)降到O(n)或O(m)。如果只依賴于左側(cè)或上方的幾個(gè)狀態(tài)甚至可能優(yōu)化到O(1)。在優(yōu)化前務(wù)必先寫出清晰正確的二維DP代碼。動(dòng)態(tài)規(guī)劃的魅力在于一旦你突破了“定義子問題”這個(gè)思維屏障很多看似復(fù)雜的問題都會(huì)變得有跡可循。它鍛煉的是一種將復(fù)雜問題分解、定義、重組的能力這種能力不僅在算法競賽中有用在解決實(shí)際的工程和系統(tǒng)設(shè)計(jì)問題時(shí)也同樣寶貴。從LIS這個(gè)經(jīng)典案例入手仔細(xì)體會(huì)每一步思考的由來然后嘗試去解構(gòu)其他DP問題你會(huì)發(fā)現(xiàn)自己對(duì)算法的理解正在從“背誦”走向“創(chuàng)造”。