【C++】動態規劃從入門到精通

一、動態規劃基礎概念詳解

什么是動態規劃
動態規劃（Dynamic Programming，DP）是一種通過將復雜問題分解為重疊子問題，并存儲子問題解以避免重復計算的優化算法。它適用于具有以下兩個關鍵性質的問題：

最優子結構：問題的最優解包含子問題的最優解

重疊子問題：不同決策序列會重復求解相同的子問題

下面用一些例子（由淺入深）了解動態規劃

1.1 斐波那契數列遞歸實現解析

int fib(int n) {if(n <= 1) return n;          // 基準條件：F(0)=0, F(1)=1return fib(n-1) + fib(n-2);  // 遞歸分解為兩個子問題
}

代碼解析：

遞歸終止條件：當n<=1時直接返回n值
遞歸關系：F(n) = F(n-1) + F(n-2)
問題分析：計算F(5)需要計算F(4)和F(3)，而計算F(4)又需要F(3)和F(2)，存在大量重復計算
時間復雜度：二叉樹結構，O(2^n)，空間復雜度O(n)（調用棧深度）

1.2 記憶化遞歸實現解析

int memo[100] = {0};  // 全局記憶數組，默認初始化為0int fib_memo(int n) {if(n <= 1) return n;if(memo[n] != 0)  // 檢查是否已計算過return memo[n];return memo[n] = fib_memo(n-1) + fib_memo(n-2);  // 計算結果并存儲
}

代碼解析：

memo數組存儲已計算結果，初始值為0表示未計算
每次遞歸調用前檢查是否已有緩存結果
通過空間換時間，將重復計算轉化為查表操作
時間復雜度優化到O(n)，空間復雜度O(n)

1.3 迭代法實現解析

int fib_tab(int n) {if(n == 0) return 0;int dp[n+1];          // 創建DP表dp[0] = 0;            // 初始化基礎條件dp[1] = 1;for(int i=2; i<=n; ++i)dp[i] = dp[i-1] + dp[i-2];  // 遞推填充表格return dp[n];
}

代碼解析：

dp數組索引對應斐波那契數列的位置
初始化前兩個已知值
循環從2開始逐步構建后續結果
時間復雜度O(n)，空間復雜度O(n)（可優化為O(1)）

二、經典問題深度解析

2.1 最長公共子序列（LCS）完整解析

問題描述：給定兩個字符串text1和text2，返回它們的最長公共子序列的長度

int lcs(string text1, string text2) {int m = text1.size(), n = text2.size();// 創建(m+1)x(n+1)的二維DP表，+1是為了處理空字符串的情況vector<vector<int>> dp(m+1, vector<int>(n+1, 0));for(int i=1; i<=m; ++i) {for(int j=1; j<=n; ++j) {if(text1[i-1] == text2[j-1])  // 字符匹配（注意索引偏移）dp[i][j] = dp[i-1][j-1] + 1;else  // 不匹配時取兩個可能方向的最大值dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];
}

代碼解析：

狀態定義：dp[i][j]表示text1前i個字符與text2前j個字符的LCS長度
初始化：第一行和第一列初始為0，表示空字符串的情況
狀態轉移：
- 當字符匹配時：LCS長度+1，繼承左上方值+1
- 當字符不匹配時：取上方或左方的最大值
遍歷順序：雙重循環按行填充表格
示例分析：
text1 = “abcde”, text2 = “ace”
DP表最終值為3（LCS為"ace"）

2.2 0-1背包問題完整解析

問題描述：給定物品重量數組wt和價值數組val，背包容量W，求能裝的最大價值

int knapsack(int W, vector<int>& wt, vector<int>& val) {int n = wt.size();vector<int> dp(W+1, 0);  // 一維DP數組優化空間for(int i=0; i<n; ++i) {            // 遍歷每個物品for(int w=W; w>=wt[i]; --w) {   // 逆序更新防止覆蓋dp[w] = max(dp[w],                    // 不選當前物品dp[w - wt[i]] + val[i]);  // 選擇當前物品}}return dp[W];
}

代碼解析：

狀態定義：dp[w]表示容量為w時的最大價值
空間優化：使用一維數組替代二維數組
逆序遍歷原因：保證每個物品只被考慮一次，避免重復使用
狀態轉移方程分析：
- 不選物品i：價值保持dp[w]不變
- 選物品i：價值為dp[w-wt[i]] + val[i]
示例分析：
W=4, wt=[2,3,4], val=[3,4,5]
最終dp[4] = max(不選4: dp[4], 選4: dp[0]+5) = 5

2.3 編輯距離完整解析

問題描述：計算將word1轉換成word2所需的最小操作次數（插入、刪除、替換）

int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();vector<vector<int>> dp(m+1, vector<int>(n+1, 0));// 初始化邊界條件for(int i=0; i<=m; ++i) dp[i][0] = i;  // 刪除i次for(int j=0; j<=n; ++j) dp[0][j] = j;  // 插入j次for(int i=1; i<=m; ++i) {for(int j=1; j<=n; ++j) {if(word1[i-1] == word2[j-1]) {  // 字符相同無需操作dp[i][j] = dp[i-1][j-1];} else {  // 選擇三種操作中的最小代價dp[i][j] = 1 + min({dp[i-1][j],   // 刪除word1字符dp[i][j-1],   // 插入word2字符dp[i-1][j-1]});// 替換字符}}}return dp[m][n];
}

代碼解析：

狀態定義：dp[i][j]表示轉換前i個字符到前j個字符的最小操作數
邊界初始化：
- 第一列表示將word1刪成空串的操作次數
- 第一行表示將空串插入成word2的操作次數
狀態轉移分析：
- 字符匹配：直接繼承左上方值
- 字符不匹配：取三種操作的最小值+1
操作類型對應關系：
- 刪除：相當于處理word1的前i-1個字符
- 插入：相當于處理word2的前j-1個字符
- 替換：相當于處理i-1和j-1的情況后修改字符
示例分析：
word1 = “horse”, word2 = “ros”
最終編輯距離為3（替換h→r，刪除 r，刪除 e）

三、動態規劃優化技巧詳解

3.1 斐波那契數列空間優化

int fib_opt(int n) {if(n == 0) return 0;int prev = 0, curr = 1;  // 初始值F(0)=0, F(1)=1for(int i=2; i<=n; ++i) {int next = prev + curr;  // 計算下一個值prev = curr;  // 更新前一個值curr = next;  // 更新當前值}return curr;
}

優化原理：

觀察發現每個狀態只依賴前兩個狀態
使用兩個變量代替數組存儲歷史值
空間復雜度從O(n)降到O(1)
滾動更新機制：
- 每次迭代將prev更新為前一個curr
- curr更新為新的計算結果

3.2 背包問題空間優化

// 二維原始版本
int dp[n+1][W+1]; // 優化為一維數組
vector<int> dp(W+1, 0);

優化原理：

二維數組中每一行只依賴上一行的數據
逆序更新避免覆蓋未使用的舊值
關鍵點：內層循環必須從W到wt[i]逆序進行
示例說明：
- 正序更新會導致物品被重復選取（完全背包問題）
- 逆序更新保證每個物品只被考慮一次

四、動態規劃解題方法論

4.1 狀態定義技巧

確定問題變量維度：
- 單序列問題（如LIS）：一維狀態dp[i]
- 雙序列問題（如LCS）：二維狀態dp[i][j]
- 帶約束問題（如背包）：二維狀態dp[i][w]
常見狀態定義模式：
- “前i個元素…”：如dp[i]表示前i個元素的最優解
- “以第i個元素結尾…”：如最長遞增子序列問題
- “位置(i,j)…”：如矩陣路徑問題

4.2 狀態轉移方程建立

分析子問題關系：
- 如何從較小規模的子問題推導當前問題
- 舉例：在編輯距離中，三種操作對應三種子問題轉移路徑
方程建立步驟：
(1) 列出所有可能的決策選項
(2) 計算每個決策對應的子問題解
(3) 選擇最優決策并組合結果

4.3 初始化技巧

邊界條件處理：
- 空字符串/空集合的處理
- 初始值的物理意義（如背包容量為0時價值為0）

特殊值初始化示例：

// 矩陣路徑問題初始化第一行和第一列
for(int i=0; i<m; ++i) dp[i][0] = 1;
for(int j=0; j<n; ++j) dp[0][j] = 1;

五、綜合案例分析

5.1 最大子數組和

問題描述：求整數數組中和最大的連續子數組

int maxSubArray(vector<int>& nums) {int currMax = nums[0], globalMax = nums[0];for(int i=1; i<nums.size(); ++i) {// 決策：繼續擴展子數組 or 重新開始currMax = max(nums[i], currMax + nums[i]);// 更新全局最大值globalMax = max(globalMax, currMax);}return globalMax;
}

算法解析：

狀態定義：currMax表示以當前元素結尾的最大子數組和
狀態轉移方程：
currMax = max(nums[i], currMax + nums[i])
空間優化：僅需維護兩個變量
示例分析：
輸入：[-2,1,-3,4,-1,2,1,-5,4]
輸出：6（子數組[4,-1,2,1]）

5.2 不同路徑問題

問題描述：m x n網格從左上角到右下角的唯一路徑數

int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 1));for(int i=1; i<m; ++i) {for(int j=1; j<n; ++j) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];
}

算法解析：

狀態定義：dp[i][j]表示到達(i,j)的路徑數
狀態轉移方程：dp[i][j] = 上方路徑數 + 左方路徑數
初始化技巧：第一行和第一列都只有1種路徑
空間優化：可用一維數組替代，dp[j] += dp[j-1]

六、動態規劃調試技巧

6.1 DP表可視化

打印DP表中間狀態

// 在LCS代碼中插入調試輸出
for(auto& row : dp) {for(int val : row) cout << val << " ";cout << endl;
}

觀察表數據是否符合預期

6.2 邊界測試用例

空輸入測試：空字符串、空數組等
極值測試：n=0, W=0等特殊情況
示例測試：使用題目給出的示例驗證

6.3 常見錯誤排查

數組越界：檢查索引是否正確（特別是從1開始的情況）
初始化錯誤：驗證邊界條件是否正確設置
循環順序錯誤：檢查是否按正確依賴順序填充表格
狀態轉移方程錯誤：用簡單用例手動驗證

七、動態規劃復雜度分析指南

7.1 時間復雜度計算

基本公式：狀態數 × 每個狀態的轉移成本
- LCS問題：O(mn)狀態 × O(1)轉移 = O(mn)
- 背包問題：O(nW)狀態 × O(1)轉移 = O(nW)
多項式時間與偽多項式時間：
- 背包問題的O(nW)稱為偽多項式時間
- 當W很大時（如指數級），算法效率會顯著下降

7.2 空間復雜度優化

滾動數組技巧：
- 二維→一維：當當前行只依賴前一行時
- 示例：斐波那契數列、背包問題
狀態壓縮技巧：
- 使用位運算表示狀態集合
- 常見于旅行商問題（TSP）等狀壓DP

八、動態規劃進階路線圖

8.1 學習路徑建議

基礎階段（1-2周）：
- 斐波那契數列
- 爬樓梯問題
- 最大子數組和
提高階段（2-4周）：
- 背包問題系列
- 字符串編輯問題
- 矩陣路徑問題
精通階段（1-2月）：
- 樹形DP（二叉樹最大路徑和）
- 狀態壓縮DP（TSP問題）
- 區間DP（矩陣鏈乘法）

8.2 推薦練習題目

題目類型	LeetCode題號	難度
爬樓梯	70	簡單
最長遞增子序列	300	中等
零錢兌換	322	中等
正則表達式匹配	10	困難
買賣股票最佳時機	121/123	中等

九、動態規劃代碼模板庫

9.1 一維DP模板

int dp[n]; 
dp[0] = initial_value;for(int i=1; i<n; ++i) {dp[i] = compute(dp[...]);
}return dp[n-1];

9.2 二維DP模板

vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化邊界
for(int i=0; i<m; ++i) dp[i][0] = ...;
for(int j=0; j<n; ++j) dp[0][j] = ...;// 填充表格
for(int i=1; i<m; ++i) {for(int j=1; j<n; ++j) {dp[i][j] = compute(dp[i-1][j], dp[i][j-1], ...);}
}