動態規劃十大經典題目整理

1. 0-1 背包問題（0-1 Knapsack Problem）

• LeetCode題號：無直接對應
• 洛谷OJ題號：P1048
• 狀態轉移方程：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
• C++代碼模板：

int dp[capacity + 1] = {0};
for (int i = 0; i < n; ++i) {for (int j = capacity; j >= weight[i]; --j) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

2. 完全背包問題（Complete Knapsack Problem）

• LeetCode題號：322
• 洛谷OJ題號：P1616
• 狀態轉移方程：dp[j] = min(dp[j], dp[j - coins[i]] + 1)
• C++代碼模板：

vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); ++i) {for (int j = coins[i]; j <= amount; ++j) {if (dp[j - coins[i]] != INT_MAX) {dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}
}

3. 編輯距離（Edit Distance）

• LeetCode題號：72

• 洛谷OJ題號：P2758

• 狀態轉移方程：

  • 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
  • 否則：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

• C++代碼模板：

vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][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];elsedp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;}
}

4. 最長公共子序列（Longest Common Subsequence）

• LeetCode題號：1143

• 洛谷OJ題號：P1439

• 狀態轉移方程：

  • 若 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
  • 否則：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

• C++代碼模板：

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;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}
}

5. 最長遞增子序列（Longest Increasing Subsequence）

• LeetCode題號：300
• 洛谷OJ題號：P1439
• 狀態轉移方程：dp[i] = max(dp[j] + 1), j < i 且 nums[j] < nums[i]
• C++代碼模板：

vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);}
}

6. 乘積最大子數組（Maximum Product Subarray）

• LeetCode題號：152
• 洛谷OJ題號：無直接對應
• 狀態轉移方程：記錄當前最大值與最小值
• C++代碼模板：

int max_prod = nums[0], min_prod = nums[0], result = nums[0];
for (int i = 1; i < n; ++i) {if (nums[i] < 0) swap(max_prod, min_prod);max_prod = max(nums[i], max_prod * nums[i]);min_prod = min(nums[i], min_prod * nums[i]);result = max(result, max_prod);
}

7. 不同路徑（Unique Paths）

• LeetCode題號：62
• 洛谷OJ題號：P1002
• 狀態轉移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• C++代碼模板：

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];}
}

8. 最小路徑和（Minimum Path Sum）

• LeetCode題號：64
• 洛谷OJ題號：P1216
• 狀態轉移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
• C++代碼模板：

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

9. 打家劫舍（House Robber）

• LeetCode題號：198
• 洛谷OJ題號：P1980（近似）
• 狀態轉移方程：dp[i] = max(dp[i-2] + nums[i], dp[i-1])
• C++代碼模板：

if (nums.empty()) return 0;
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); ++i) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}

10. 最長有效括號（Longest Valid Parentheses）

• LeetCode題號：32
• 洛谷OJ題號：無
• 狀態轉移方程：復雜，涉及匹配與回溯邏輯
• C++代碼模板：

int max_len = 0;
vector<int> dp(s.length(), 0);
for (int i = 1; i < s.length(); ++i) {if (s[i] == ')') {if (s[i - 1] == '(')dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;max_len = max(max_len, dp[i]);}
}