动态规划应用场景 + 代表题目清单（模板加上套路加上题单）
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])
}