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