深入淺出掌握動態規劃核心思想，圖文并茂+實戰代碼

什么是動態規劃？

動態規劃（Dynamic Programming, DP） 是一種高效解決多階段決策問題的方法。它通過將復雜問題分解為重疊子問題，并存儲子問題的解（避免重復計算），最終解決原問題。

動態規劃適用場景

• 重疊子問題：問題可分解為重復出現的子問題

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

• 無后效性：當前狀態一旦確定，后續決策不受之前決策影響

一、從斐波那契數列入門（記憶化搜索）

斐波那契數列是理解DP思想的完美起點：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

1.1 遞歸解法（低效）

int fib(int n) {if (n <= 1) return n;return fib(n-1) + fib(n-2);
}

問題：存在大量重復計算，時間復雜度O(2^n)

1.2 記憶化搜索（自頂向下）

#include <vector>
using namespace std;int fibMemo(int n, vector<int>& memo) {if (n <= 1) return n;if (memo[n] != -1) return memo[n]; // 已計算過memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);return memo[n];
}int fib(int n) {vector<int> memo(n+1, -1); // 初始化記憶數組return fibMemo(n, memo);
}

優點：時間復雜度降為O(n)，空間復雜度O(n)

二、數塔問題（經典DP）

問題描述：從塔頂到塔底，每次只能向下或右下移動，求最大路徑和。

        5/ \8   3/ \ / \12  7  16/ \ / \ / \4   10  11  6

2.1 DP解法思路

1. 狀態定義：dp[i][j]表示從第i行第j列出發到底部的最大路徑和

2. 狀態轉移：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])

3. 邊界條件：最底層dp值等于元素本身

2.2 C++實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxPathSum(vector<vector<int>>& tower) {int n = tower.size();vector<vector<int>> dp(n, vector<int>(n, 0));// 初始化最后一行for (int j = 0; j < n; ++j) dp[n-1][j] = tower[n-1][j];// 自底向上計算for (int i = n-2; i >= 0; --i) {for (int j = 0; j <= i; ++j) {dp[i][j] = tower[i][j] + max(dp[i+1][j], dp[i+1][j+1]);}}return dp[0][0];
}int main() {vector<vector<int>> tower = {{5},{8, 3},{12, 7, 16},{4, 10, 11, 6}};cout << "最大路徑和: " << maxPathSum(tower) << endl; // 輸出: 5+8+7+11=31return 0;
}

三、最長上升子序列（LIS）

問題描述：給定數組，找到最長嚴格遞增子序列的長度 示例：[10,9,2,5,3,7,101,18] -> 最長上升子序列[2,5,7,101]長度為4

3.1 DP解法

1. 狀態定義：dp[i]表示以nums[i]結尾的LIS長度

2. 狀態轉移：

3. 結果：max(dp[0...n-1])

3.2 C++實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;vector<int> dp(nums.size(), 1);int maxLen = 1;for (int i = 1; i < nums.size(); ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);}return maxLen;
}int main() {vector<int> nums = {10,9,2,5,3,7,101,18};cout << "最長上升子序列長度: " << lengthOfLIS(nums) << endl; // 輸出4return 0;
}

時間復雜度：O(n2) 優化：二分查找可優化至O(nlogn)

四、0-1背包問題（經典DP）

問題描述：給定n件物品（重量w[i], 價值v[i]）和容量為C的背包，如何裝包使總價值最大？

4.1 DP解法思路

1. 狀態定義：dp[i][j]表示前i件物品放入容量為j的背包的最大價值

2. 狀態轉移：

4.2 C++實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int knapsack(int C, vector<int>& w, vector<int>& v) {int n = w.size();vector<vector<int>> dp(n+1, vector<int>(C+1, 0));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= C; ++j) {if (j < w[i-1]) {  // 注意下標偏移dp[i][j] = dp[i-1][j];} else {dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j - w[i-1]]);}}}return dp[n][C];
}int main() {vector<int> weights = {2, 3, 4, 5};  // 物品重量vector<int> values = {3, 4, 5, 6};   // 物品價值int capacity = 8;                    // 背包容量cout << "最大價值: " << knapsack(capacity, weights, values) << endl; // 輸出: 10 (選3+5+6)return 0;
}

五、動態規劃解題步驟總結

1. 定義狀態：明確dp數組的含義

2. 確定轉移方程：關鍵步驟，找出狀態間關系

3. 初始化：設置邊界值

4. 確定計算順序：自底向上或自頂向下

5. 輸出結果：從最終狀態獲取答案

6. 空間優化：滾動數組等技巧（可選）

六、常見DP模型

問題類型	典型問題	狀態轉移特征
線性DP	最長上升子序列	沿數組順序轉移
區間DP	矩陣鏈乘法、石子合并	從小區間向大區間轉移
背包問題	0-1背包、完全背包	物品選擇決策
樹形DP	二叉樹最大路徑和	在樹結構上遞歸轉移
狀態壓縮DP	旅行商問題(TSP)	用二進制表示狀態

掌握動態規劃需要多練習！建議從LeetCode簡單DP題開始，逐步提升難度。

推薦練習：

• 70. 爬樓梯

• 53. 最大子數組和

• 322. 零錢兌換

• 1143. 最長公共子序列

通過本文的學習，相信你已經掌握了動態規劃的基本思想和常見問題的解決方法。繼續堅持練習，很快你就能在算法解題中靈活運用DP技巧！