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