1. 序列型DP（Sequence DP）
? 應用場景
-
單個或多個序列（數組/字符串），求最優子結構。
-
常見問題：最長遞增子序列、最長公共子序列、回文子序列。
🧠 套路總結
-
單序列：dp[i] = max(dp[j]) + 1 (j < i 且 nums[j] < nums[i])
-
雙序列：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1) 依賴匹配關系
🧪 代表題目
1.1 最長遞增/最長遞減子序列
-
題目舉例
-
LeetCode 300. Longest Increasing Subsequence
-
LeetCode 674. Longest Continuous Increasing Subsequence
-
LeetCode 646. Maximum Length of Pair Chain
-
LeetCode 376. Wiggle Subsequence
-
1.2 最長公共子序列/子串
-
題目舉例
-
LeetCode 1143. Longest Common Subsequence
-
LeetCode 1092. Shortest Common Supersequence
-
LeetCode 718. Maximum Length of Repeated Subarray
-
1.3 回文子序列/子串
-
題目舉例
-
LeetCode 516. Longest Palindromic Subsequence
-
LeetCode 5. Longest Palindromic Substring
-
LeetCode 647. Palindromic Substrings
-
1.4 編輯距離和相似度
-
題目舉例
-
LeetCode 72. Edit Distance
-
LeetCode 583. Delete Operation for Two Strings
-
🧩 Go 模板
for i := 1; i < n; i++ {for j := 0; j < i; j++ {if condition {dp[i] = max(dp[i], dp[j] + val)}}
}
2. 背包型DP（Knapsack DP）
? 應用場景
-
有物品、價值、容量的選擇問題。
-
子類型：0/1背包、完全背包、多重背包。
🧠 套路總結
// 0/1 背包（從大到小）
for i := 0; i < n; i++ {for j := cap; j >= weight[i]; j-- {dp[j] = max(dp[j], dp[j-weight[i]]+value[i])}
}// 完全背包（從小到大）
for i := 0; i < n; i++ {for j := weight[i]; j <= cap; j++ {dp[j] = max(dp[j], dp[j-weight[i]]+value[i])}
}
🧪 代表題目
2.1 0/1背包問題
-
題目舉例
-
LeetCode 416. Partition Equal Subset Sum
-
LeetCode 1049. Last Stone Weight II
-
LeetCode 474. Ones and Zeroes
-
2.2 完全背包問題
-
題目舉例
-
LeetCode 518. Coin Change II
-
LeetCode 322. Coin Change
-
LeetCode 139. Word Break
-
2.3 多重背包、分組背包等變形
-
題目舉例
-
LeetCode 698. Partition to K Equal Sum Subsets
-
LeetCode 474. Ones and Zeroes (也包含組背包思想)
-
3. 區間型DP（Interval DP）
? 應用場景
-
合并區間、回文判斷，求最優合并方案。
-
狀態：dp[i][j]表示區間[i,j]的最優值。
🧠 套路總結
for length := 2; length <= n; length++ {for i := 0; i <= n-length; i++ {j := i + length - 1for k := i; k < j; k++ {dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+cost[i][j])}}
}
🧪 代表題目
3.1 合并區間與括號相關
-
題目舉例
-
LeetCode 312. Burst Balloons
-
LeetCode 1000. Minimum Cost to Merge Stones
-
LeetCode 544. Output Contest Matches
-
3.2 回文串判定與劃分
-
題目舉例
-
LeetCode 5. Longest Palindromic Substring
-
LeetCode 132. Palindrome Partitioning II
-
LeetCode 131. Palindrome Partitioning
-
4. 狀態壓縮DP（Bitmask DP）
? 應用場景
-
元素子集、排列組合、旅行商問題等。
-
狀態數 ≈ 2^n（n ≤ 20）
🧠 套路總結
for mask := 0; mask < (1<<n); mask++ {for i := 0; i < n; i++ {if (mask&(1<<i)) == 0 {newMask := mask | (1 << i)dp[newMask] = min(dp[newMask], dp[mask]+cost[prev][i])}}
}
🧪 代表題目
4.1 旅行商（TSP）
-
題目舉例
-
LeetCode 847. Shortest Path Visiting All Nodes
-
LeetCode 1129. Shortest Path with Alternating Colors
-
4.2 子集劃分和集合覆蓋
-
題目舉例
-
LeetCode 698. Partition to K Equal Sum Subsets
-
LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps
-
5. 樹形DP（Tree DP）
? 應用場景
-
狀態在樹上自底向上傳遞，依賴子樹結構。
🧠 套路總結
func dfs(node *TreeNode) (rob, notRob int) {if node == nil {return 0, 0}leftRob, leftNot := dfs(node.Left)rightRob, rightNot := dfs(node.Right)rob = node.Val + leftNot + rightNotnotRob = max(leftRob, leftNot) + max(rightRob, rightNot)return
}
🧪 代表題目
-
5.1 樹上選點問題
-
題目舉例
-
LeetCode 337. House Robber III
-
LeetCode 87. Scramble String (也用樹形DP思想)
-
-
題目舉例
-
LeetCode 124. Binary Tree Maximum Path Sum
-
LeetCode 968. Binary Tree Cameras
-
-
5.2 樹上路徑問題
6. 計數型DP（Counting DP）
? 應用場景
-
統計路徑、方案數、組合數。
🧠 套路總結
for i := 0; i < m; i++ {for j := 0; j < n; j++ {if i > 0 {dp[i][j] += dp[i-1][j]}if j > 0 {dp[i][j] += dp[i][j-1]}}
}
🧪 代表題目
-
6.1 路徑計數
-
題目舉例
-
LeetCode 62. Unique Paths
-
LeetCode 63. Unique Paths II
-
-
6.2 組合計數
-
題目舉例
-
LeetCode 70. Climbing Stairs
-
LeetCode 639. Decode Ways II
-
-
題目舉例
-
LeetCode 377. Combination Sum IV
-
-
6.3 排列計數
- LeetCode 377. Combination Sum IV
7. 概率型DP（Probability DP）
? 應用場景
-
求概率、期望值。
🧠 套路總結
for k := 1; k <= K; k++ {for i := 0; i < N; i++ {for j := 0; j < N; j++ {for _, dir := range dirs {ni, nj := i+dir[0], j+dir[1]if inBounds(ni, nj) {dp[k][i][j] += dp[k-1][ni][nj] / 8.0}}}}
}
🧪 代表題目
7.1 馬爾可夫過程概率計算
-
題目舉例
-
LeetCode 688. Knight Probability in Chessboard
-
LeetCode 837. New 21 Game
-
7.2 期望值計算
-
題目舉例
-
LeetCode 470. Implement Rand10() Using Rand7()
-
? 8. 子串 / 子序列問題
多用于字符串匹配、編輯距離等
🔹 場景：
-
最長公共子序列、子串
-
編輯距離
-
回文子序列
🔸 代表題目：
| 題號 | 名稱 |
|---|---|
| 1143 | Longest Common Subsequence |
| 72 | Edit Distance |
| 5 | Longest Palindromic Substring |
📌 模板結構：
if s[i] == t[j] {dp[i][j] = dp[i-1][j-1] + 1
} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
