动态规划算法详解：从入门到精通

动态规划（Dynamic Programming）是算法竞赛中最重要的技术之一，本文将系统讲解各类DP问题的原理、状态设计和优化技巧。

📚 目录

  1. 动态规划基础
  2. 线性DP
  3. 背包DP
  4. 区间DP
  5. 数位DP
  6. 状压DP
  7. 树形DP
  8. 轮廓线DP

🎯 动态规划基础

什么是动态规划？

核心思想： 将复杂问题分解为子问题，通过存储子问题的解来避免重复计算。

三要素：

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：递归过程中重复计算相同的子问题
  3. 无后效性：某阶段的状态一旦确定，不受后续决策影响

DP的设计步骤：

  1. 确定状态：dp[i] 表示什么？
  2. 状态转移方程：如何从子问题推导到当前问题？
  3. 初始状态：边界条件是什么？
  4. 计算顺序：如何保证计算某个状态时其依赖的状态已计算？

动态规划 vs 贪心 vs 分治

特性 动态规划 贪心算法 分治算法
子问题 重叠 独立 独立
最优性 全局最优 局部最优 全局最优
决策 考虑所有选择 只考虑当前最优 递归求解

1️⃣ 线性DP

1.1 最长上升子序列（LIS）

问题描述：
给定一个长度为 的序列，求最长上升子序列的长度。

状态定义：

  • dp[i] 表示以 arr[i] 结尾的最长上升子序列长度

状态转移方程：

  • 初始化：dp[i] = 1（每个元素自己构成长度为1的子序列）

  • 转移过程：枚举所有 j < i，如果 arr[j] < arr[i]，则：

  • 最终答案：

时间复杂度：

代码实现（O(n²) 解法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int n;
int arr[MAXN];
int dp[MAXN];

int lis() {
    int maxLen = 0;
    
    for (int i = 0; i < n; i++) {
        dp[i] = 1;  // 至少包含自己
        
        // 枚举前面的元素
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << lis() << endl;
    
    return 0;
}

优化：O(n log n) 解法

使用贪心 + 二分查找优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lis_fast(vector<int>& arr) {
    vector<int> tail;  // tail[i] 表示长度为 i+1 的上升子序列的最小结尾元素
    
    for (int x : arr) {
        // 二分查找第一个 >= x 的位置
        auto it = lower_bound(tail.begin(), tail.end(), x);
        
        if (it == tail.end()) {
            tail.push_back(x);  // 可以延长最长子序列
        } else {
            *it = x;  // 替换为更小的元素
        }
    }
    
    return tail.size();
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << lis_fast(arr) << endl;
    
    return 0;
}

1.2 最长公共子序列（LCS）

问题描述：
给定两个序列 和 ，求它们的最长公共子序列长度。

状态定义：

  • dp[i][j] 表示字符串 的前 个字符和字符串 的前 个字符的最长公共子序列长度

状态转移方程：

  • 如果 （当前字符相同）：

  • 如果 （当前字符不同）：

时间复杂度：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];

int lcs(string a, string b) {
    int n = a.length();
    int m = b.length();
    
    // 初始化边界
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int j = 0; j <= m; j++) dp[0][j] = 0;
    
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[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[n][m];
}

int main() {
    string a, b;
    cin >> a >> b;
    cout << lcs(a, b) << endl;
    return 0;
}

1.3 最大子段和

问题描述：
给定一个长度为 的序列，求连续子序列的最大和。

💡 问题理解：
想象你在炒股,数组表示每天的收益(可能为负),你要找一个连续的时间段,使得这段时间的总收益最大。

🎯 核心思路：
对于每个位置 ,我们考虑:

  1. 要不要把前面的子段带上？
    • 如果 dp[i-1] > 0,说明前面的子段对我们有帮助,加上它
    • 如果 dp[i-1] ≤ 0,说明前面的子段是累赘,不如从当前位置重新开始

状态定义：

  • dp[i] 表示以 arr[i] 结尾的最大子段和

⚠️ 注意:是”以 arr[i] 结尾”,不是”前 i 个元素的最大子段和”!

状态转移方程：

👨‍🏫 转移方程的含义：

  • dp[i-1] + arr[i]:把当前元素接到前面的最优子段后面
  • arr[i]:从当前元素重新开始

时间复杂度：
空间复杂度： ,可优化到

📊 手动模拟过程

示例数组： [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i arr[i] dp[i-1] dp[i-1] + arr[i] arr[i] dp[i] 决策
0 -2 - - -2 -2 起点
1 1 -2 -1 1 1 重新开始
2 -3 1 -2 -3 -2 继续前面
3 4 -2 2 4 4 重新开始
4 -1 4 3 -1 3 继续前面
5 2 3 5 2 5 继续前面
6 1 5 6 1 6 继续前面
7 -5 6 1 -5 1 继续前面
8 4 1 5 4 5 继续前面

最大值:dp[6] = 6,对应子段 [4, -1, 2, 1]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int n;
int arr[MAXN];
long long dp[MAXN];

long long maxSubArray() {
    dp[0] = arr[0];
    long long maxSum = dp[0];
    
    for (int i = 1; i < n; i++) {
        // 核心决策：要不要接上前面的子段？
        dp[i] = max((long long)arr[i], dp[i-1] + arr[i]);
        maxSum = max(maxSum, dp[i]);
    }
    
    return maxSum;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << maxSubArray() << endl;
    
    return 0;
}

💡 代码说明：

  1. dp[0] = arr[0]:第一个元素只能是自己
  2. 遍历时不断更新 maxSum,因为最大子段可能在中间某处结束
  3. 使用 long long 防止溢出

🚀 空间优化： 只需要一个变量存储 dp[i-1]

1
2
3
4
5
6
7
8
9
10
11
long long maxSubArray_optimized() {
    long long curSum = arr[0];  // 当前以 arr[i] 结尾的最大子段和
    long long maxSum = arr[0];  // 全局最大值
    
    for (int i = 1; i < n; i++) {
        curSum = max((long long)arr[i], curSum + arr[i]);
        maxSum = max(maxSum, curSum);
    }
    
    return maxSum;
}

💡 优化说明：

  • 我们只需要知道 dp[i-1] 的值,不需要保存整个数组
  • 用 curSum 滚动更新,空间复杂度降到

❓ 常见问题 Q&A

Q1: 为什么状态定义是”以 arr[i] 结尾”而不是”前 i 个元素的最大子段和”？

A: 如果定义成”前 i 个元素的最大子段和”,转移会很麻烦:

  • 最大子段可能不包含 arr[i]
  • 无法确定是否要把 arr[i] 加进来

而”以 arr[i] 结尾”强制包含当前元素,决策变简单:

  • 要么接上前面:dp[i-1] + arr[i]
  • 要么重新开始:arr[i]

Q2: 如果所有数都是负数怎么办？

A: 返回最大的那个负数(最小的损失)。代码自然处理这种情况。

Q3: 如何记录最大子段的起始和结束位置？

A: 增加两个变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int start = 0, end = 0;  // 最优子段的起止位置
int tempStart = 0;       // 临时起点

for (int i = 1; i < n; i++) {
    if (curSum + arr[i] < arr[i]) {
        curSum = arr[i];
        tempStart = i;  // 重新开始,更新起点
    } else {
        curSum += arr[i];
    }
    
    if (curSum > maxSum) {
        maxSum = curSum;
        start = tempStart;
        end = i;
    }
}

Q4: 能用分治法做吗？

A: 可以!时间复杂度 ,不如DP高效,但思路很巧妙:

  • 最大子段要么在左半部分
  • 要么在右半部分
  • 要么跨越中点

Q5: 这道题和股票问题有什么关系？

A: 密切相关!

  • 如果数组表示”第i天卖出比买入多赚的钱”
  • 最大子段和就是”最佳买卖时机的最大利润”

⚠️ 常见错误

❌ 错误1:忘记初始化 maxSum

1
long long maxSum = 0;  // 错误!如果所有数都是负数,答案应该是最大的负数

✅ 正确:

1
long long maxSum = dp[0];  // 或 arr[0]

❌ 错误2:混淆 dp[i] 的含义

1
2
// 错误理解:dp[i] = 前i个元素的最大子段和
dp[i] = max(dp[i-1], arr[i]);  // 这是错的!

✅ 正确:dp[i] 必须以 arr[i] 结尾

1
dp[i] = max(dp[i-1] + arr[i], arr[i]);

❌ 错误3:返回 dp[n-1]

1
return dp[n-1];  // 错误!最大子段可能不在最后

✅ 正确:返回所有 dp[i] 的最大值

1
return maxSum;  // 在遍历过程中不断更新

🎯 变形题目

1. 最大子矩阵和(二维版本)

  • 枚举上下边界,把每列压缩成一个数,转化为一维问题
  • 时间复杂度: 或

2. 环形数组的最大子段和

  • 最大子段要么不跨越边界,要么跨越边界
  • 不跨越:正常求最大子段和
  • 跨越:总和 - 最小子段和

3. 至少包含 k 个元素的最大子段和

  • 先求出前 k 个元素的和作为初始值
  • 然后用滑动窗口 + DP

4. 最多删除一个元素的最大子段和

  • dp[i][0]:不删除,以i结尾的最大和
  • dp[i][1]:删除一个,以i结尾的最大和

💪 练习建议

  1. LeetCode 53 - Maximum Subarray(原题)
  2. LeetCode 152 - Maximum Product Subarray(乘积版本)
  3. LeetCode 918 - Maximum Sum Circular Subarray(环形数组)
  4. LeetCode 1191 - K-Concatenation Maximum Sum(重复数组)

2️⃣ 背包DP

2.1 0-1背包

问题描述：
有 个物品，每个物品有重量 和价值 。背包容量为 ，每个物品只能选一次，求最大价值。

💡 生活类比：
你去超市购物,每个商品有价格(重量)和满意度(价值),钱包只能装下总价 的商品。每种商品只有一件,如何选择才能让总满意度最大?

🎯 核心思路：
对于每个物品,我们有两种选择:

  1. 选它:获得它的价值,但要占用背包空间
  2. 不选它:不占空间,但没有价值

关键是:每个物品只能选一次!

状态定义：

  • dp[i][j] 表示考虑前 个物品,背包容量为 时的最大价值

👨‍🏫 状态含义详解:

  • 前 个物品:可以选也可以不选,但不能选第 及之后的
  • 容量为 :剩余可用空间是
  • 最大价值:所有合法方案中的价值最大值

状态转移方程：

📊 转移方程分解:

  • dp[i-1][j]:不选第 个物品,价值等于前 个物品在容量 时的最优解
  • dp[i-1][j-w[i]] + v[i]:选第 个物品
    • 需要先留出 的空间
    • 在剩余空间 中选前 个物品
    • 加上第 个物品的价值

边界条件:

  • dp[0][j] = 0:没有物品时,价值为0
  • dp[i][0] = 0:容量为0时,价值为0

时间复杂度:
空间复杂度: ,可优化到

📊 手动模拟过程

示例:

  • 物品: [(w=2,v=3), (w=3,v=4), (w=4,v=5), (w=5,v=6)]
  • 背包容量: W=8

DP表格(行=物品,列=容量):

i\j 0 1 2 3 4 5 6 7 8
0(无) 0 0 0 0 0 0 0 0 0
1(2,3) 0 0 3 3 3 3 3 3 3
2(3,4) 0 0 3 4 4 7 7 7 7
3(4,5) 0 0 3 4 5 7 8 9 9
4(5,6) 0 0 3 4 5 7 8 9 10

💡 关键步骤解释(i=2,j=5):

  • 不选物品2: dp[1][5] = 3
  • 选物品2: dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 = 7
  • 取max: dp[2][5] = 7 ✅

代码实现（二维）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int MAXW = 10005;
int n, W;
int w[MAXN], v[MAXN];
int dp[MAXN][MAXW];

int knapsack01() {
    // 初始化:第0行和第0列都是0
    for (int j = 0; j <= W; j++) dp[0][j] = 0;
    
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];  // 不选第i个物品
            
            // 如果容量够,考虑选第i个物品
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    
    return dp[n][W];
}

int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    
    cout << knapsack01() << endl;
    
    return 0;
}

🚀 空间优化（一维）

💡 优化思路:

  • 观察: dp[i][j] 只依赖于 dp[i-1][...]
  • 可以用一维数组滚动更新

⚠️ 关键: 必须倒序遍历!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[MAXW];

int knapsack01_optimized() {
    for (int j = 0; j <= W; j++) dp[j] = 0;
    
    for (int i = 1; i <= n; i++) {
        // ⚠️ 倒序遍历，避免重复使用同一物品
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

👨‍🏫 为什么要倒序遍历？

假设正序遍历:

1
2
3
4
// 错误示范!
for (int j = w[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
  • 当更新 dp[j] 时,dp[j-w[i]] 可能已经被更新过
  • 这相当于同一物品用了多次!

倒序遍历:

  • 更新 dp[j] 时,dp[j-w[i]] 还是上一轮的值
  • 保证每个物品只用一次 ✅

❓ 常见问题 Q&A

Q1: 如何输出选了哪些物品？

A: 从 dp[n][W] 倒推:

1
2
3
4
5
6
7
8
9
vector<int> items;
int j = W;
for (int i = n; i >= 1; i--) {
    if (dp[i][j] != dp[i-1][j]) {
        items.push_back(i);  // 选了第i个物品
        j -= w[i];
    }
}
reverse(items.begin(), items.end());

Q2: 如果要求恰好装满背包呢？

A: 初始化改为:

1
2
3
4
dp[0][0] = 0;           // 容量0恰好装满
for (int j = 1; j <= W; j++) {
    dp[0][j] = -INF;    // 其他容量无法装满
}

Q3: 为什么叫”0-1”背包？

A: 因为每个物品只有两种状态:

  • 0: 不选
  • 1: 选一次

Q4: 一维优化后如何输出方案？

A: 需要额外记录决策路径,或者用二维数组。一维优化只能得到最优值。

Q5: 如果有物品价值为负数怎么办？

A: 负数物品直接不选即可,DP过程不变。

⚠️ 常见错误

❌ 错误1: 一维优化时正序遍历

1
2
3
for (int j = w[i]; j <= W; j++) {  // 错误!会重复使用物品
    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}

✅ 正确: 倒序遍历

1
2
3
for (int j = W; j >= w[i]; j--) {
    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}

❌ 错误2: 忘记判断容量

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);  // 如果j<w[i]会越界!

✅ 正确: 先判断容量

1
2
3
if (j >= w[i]) {
    dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}

❌ 错误3: 混淆0-1背包和完全背包

1
2
// 0-1背包倒序,完全背包正序
for (int j = w[i]; j <= W; j++) {  // 这是完全背包!

2.2 完全背包

问题描述：
有 种物品，每种物品有无限个，求最大价值。

💡 生活类比:
便利店有无限库存,你可以买任意多个同款商品(只要钱包装得下)。

🎯 核心区别:

  • 0-1背包: 每个物品最多选1次 → 从后往前更新
  • 完全背包: 每个物品可选无限次 → 从前往后更新

状态定义:

  • dp[i][j] 表示考虑前 种物品,背包容量为 时的最大价值

状态转移方程:

👨‍🏫 转移方程详解:

  • dp[i-1][j]: 不选第 种物品(和0-1背包一样)
  • dp[i][j-w[i]] + v[i]: 选至少一个第 种物品
    • 注意是 dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]
    • 因为选了一个后,还可以继续选这种物品!

📊 转移方程推导:

为什么 dp[i][j-w[i]] 可以表示”选任意多个”？

1
2
3
4
5
6
7
dp[i][j] = max(
    dp[i-1][j],                           // 选0个
    dp[i-1][j-w[i]] + v[i],              // 选1个
    dp[i-1][j-2*w[i]] + 2*v[i],          // 选2个
    ...
    dp[i-1][j-k*w[i]] + k*v[i]           // 选k个
)

但是 dp[i][j-w[i]] 已经包含了”选0到k-1个”的最优解:

1
2
3
4
5
dp[i][j-w[i]] = max(
    dp[i-1][j-w[i]],                     // 选0个
    dp[i-1][j-2*w[i]] + v[i],            // 选1个
    ...
)

所以: dp[i][j-w[i]] + v[i] = “在最优地选若干个的基础上,再选一个”

代码实现（一维优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[MAXW];

int knapsack_complete() {
    for (int j = 0; j <= W; j++) dp[j] = 0;
    
    for (int i = 1; i <= n; i++) {
        // ⚠️ 正序遍历，允许重复使用物品
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

💡 为什么完全背包要正序遍历？

正序遍历时:

  • 更新 dp[j] 时,dp[j-w[i]] 已经更新过
  • dp[j-w[i]] 包含了”已经选了若干个物品i”的状态
  • 再加上一个物品i,实现了”无限次选择” ✅

📊 对比:0-1背包 vs 完全背包

特性 0-1背包 完全背包
每种物品 最多1个 无限个
转移方程 dp[i-1][j-w[i]] dp[i][j-w[i]]
一维优化 倒序遍历 正序遍历
原因 防止重复使用 允许重复使用

❓ 常见问题 Q&A

Q1: 为什么完全背包可以用一维数组？

A: 因为 dp[i][j] 只依赖:

  • dp[i-1][j]: 上一行同列(不选)
  • dp[i][j-w[i]]: 本行前面的(选)

正序更新时,前面的已经是”本行”的值了。

Q2: 如何输出完全背包的方案(每种物品选了几个)？

A: 需要用二维数组倒推:

1
2
3
4
5
6
7
8
for (int i = n; i >= 1; i--) {
    int count = 0;
    while (j >= w[i] && dp[i][j] == dp[i][j-w[i]] + v[i]) {
        count++;
        j -= w[i];
    }
    cout << "物品" << i << "选了" << count << "个" << endl;
}

Q3: 完全背包能用二进制优化吗？

A: 不需要!因为一维优化已经很高效了。

  • 完全背包:
  • 转化为0-1背包再优化:

反而更慢。

Q4: 如果限制每种物品最多选k个呢？

A: 这就是”多重背包”问题,见下一节。

⚠️ 常见错误

❌ 错误1: 完全背包用倒序遍历

1
2
3
for (int j = W; j >= w[i]; j--) {  // 错误!变成了0-1背包
    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}

✅ 正确: 正序遍历

1
2
3
for (int j = w[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}

❌ 错误2: 转移方程用错

1
2
// 这是0-1背包的转移!
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);

✅ 正确: 注意是 dp[i][j-w[i]]

1
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]);

🎯 练习建议

  1. LeetCode 322 - Coin Change(完全背包变形)
  2. LeetCode 518 - Coin Change 2(方案数)
  3. 洛谷 P1616 - 疯狂的采药(完全背包模板题)

2.3 多重背包

问题描述：
有 种物品，第 种物品有 个，求最大价值。

优化方法： 二进制拆分

将 个物品拆分成 组：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int w, v;
};

int knapsack_multiple(int n, int W, vector<int>& weight, vector<int>& value, vector<int>& count) {
    vector<Item> items;
    
    // 二进制拆分
    for (int i = 0; i < n; i++) {
        int c = count[i];
        for (int k = 1; k <= c; k *= 2) {
            items.push_back({weight[i] * k, value[i] * k});
            c -= k;
        }
        if (c > 0) {
            items.push_back({weight[i] * c, value[i] * c});
        }
    }
    
    // 转化为0-1背包
    vector<int> dp(W + 1, 0);
    for (auto& item : items) {
        for (int j = W; j >= item.w; j--) {
            dp[j] = max(dp[j], dp[j - item.w] + item.v);
        }
    }
    
    return dp[W];
}

3️⃣ 区间DP

核心思想： 在区间上进行动态规划，通常按区间长度递增的顺序计算。

状态定义：

  • dp[i][j] 表示区间 的最优解

状态转移：

  • 枚举分割点 ，将区间分为 和

经典例题：石子合并

问题描述：
有 堆石子排成一排，每次可以合并相邻的两堆，代价为两堆石子数量之和。求最小总代价。

状态定义：

  • dp[i][j] 表示合并区间 的最小代价
  • sum[i][j] 表示区间 的石子总数

状态转移：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int n;
int stones[MAXN];
int sum[MAXN];  // 前缀和
int dp[MAXN][MAXN];

void solve() {
    // 计算前缀和
    sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + stones[i];
    }
    
    // 初始化
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;  // 单个石子堆不需要合并
    }
    
    // 按区间长度递增
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            int cost = sum[j] - sum[i-1];  // 区间和
            
            // 枚举分割点
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
            }
        }
    }
    
    cout << dp[1][n] << endl;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stones[i];
    }
    
    solve();
    
    return 0;
}

矩阵链乘法

问题描述：
给定 个矩阵的维度，求最优的乘法顺序，使得标量乘法次数最少。

状态定义：

  • dp[i][j] 表示计算矩阵 的最小代价

状态转移：

其中 是矩阵维度数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int n;
int p[MAXN];  // p[i-1] x p[i] 是第i个矩阵的维度
int dp[MAXN][MAXN];

void matrixChainOrder() {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    
    // 按链长度递增
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            
            // 枚举分割点
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    cout << dp[1][n] << endl;
}

int main() {
    cin >> n;
    for (int i = 0; i <= n; i++) {
        cin >> p[i];
    }
    
    matrixChainOrder();
    
    return 0;
}

4️⃣ 数位DP

核心思想： 按数位逐位构造数字，统计满足条件的数字个数。

适用场景：

  • 统计区间 内满足某种性质的数字个数
  • 性质通常与数位有关

基本框架：

  • dp[pos][state][limit]
    • pos: 当前处理的数位
    • state: 状态（如前导零、数字和等）
    • limit: 是否受到原数限制

经典例题：数字计数

问题描述：
统计区间 中数字 出现的次数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>
using namespace std;

long long dp[20][20];  // dp[pos][cnt] 表示第pos位，已经有cnt个d的方案数
int digits[20];
int d;  // 要统计的数字

// pos: 当前位, cnt: 已有d的个数, limit: 是否受限, leadZero: 是否有前导零
long long dfs(int pos, int cnt, bool limit, bool leadZero) {
    if (pos == -1) return cnt;
    
    if (!limit && !leadZero && dp[pos][cnt] != -1) {
        return dp[pos][cnt];
    }
    
    int up = limit ? digits[pos] : 9;
    long long res = 0;
    
    for (int i = 0; i <= up; i++) {
        // 跳过前导零的情况
        if (leadZero && i == 0) {
            res += dfs(pos - 1, cnt, limit && i == up, true);
        } else {
            res += dfs(pos - 1, cnt + (i == d), limit && i == up, false);
        }
    }
    
    if (!limit && !leadZero) {
        dp[pos][cnt] = res;
    }
    
    return res;
}

long long count(long long x) {
    if (x < 0) return 0;
    
    int len = 0;
    while (x) {
        digits[len++] = x % 10;
        x /= 10;
    }
    
    return dfs(len - 1, 0, true, true);
}

int main() {
    long long L, R;
    cin >> L >> R >> d;
    
    memset(dp, -1, sizeof(dp));
    cout << count(R) - count(L - 1) << endl;
    
    return 0;
}

5️⃣ 状压DP

核心思想： 用二进制状态表示集合，通过位运算进行状态转移。

适用场景：

  • 集合元素较少（通常 ）
  • 需要记录选择了哪些元素

常用位运算：

  • 检查第 位：(state >> i) & 1
  • 设置第 位：state | (1 << i)
  • 清除第 位：state & ~(1 << i)
  • 翻转第 位：state ^ (1 << i)

经典例题：旅行商问题（TSP）

问题描述：
有 个城市，给定城市间距离，求从城市 0 出发，经过所有城市恰好一次后返回的最短路径。

状态定义：

  • dp[state][i] 表示已访问城市集合为 state，当前在城市 的最短路径长度

状态转移：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 20;
const int INF = 0x3f3f3f3f;
int n;
int dist[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

int tsp() {
    // 初始化
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;  // 从城市0开始
    
    // 枚举所有状态
    for (int state = 1; state < (1 << n); state++) {
        for (int i = 0; i < n; i++) {
            if (!(state & (1 << i))) continue;
            if (dp[state][i] == INF) continue;
            
            // 枚举下一个城市
            for (int j = 0; j < n; j++) {
                if (state & (1 << j)) continue;
                
                int nextState = state | (1 << j);
                dp[nextState][j] = min(dp[nextState][j], dp[state][i] + dist[i][j]);
            }
        }
    }
    
    // 返回起点
    int ans = INF;
    int fullState = (1 << n) - 1;
    for (int i = 1; i < n; i++) {
        ans = min(ans, dp[fullState][i] + dist[i][0]);
    }
    
    return ans;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    
    cout << tsp() << endl;
    
    return 0;
}

6️⃣ 树形DP

核心思想： 在树上进行动态规划，通常通过DFS计算。

状态定义：

  • dp[u][state] 表示以 为根的子树，在某种状态下的最优解

计算顺序： 后序遍历（先计算子节点，再计算父节点）

经典例题：树的直径

问题描述：
求树中最长路径的长度。

状态定义：

  • dp[u] 表示以 为根，向下延伸的最长路径长度

答案： ，其中 是 的两个子节点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int n;
vector<int> tree[MAXN];
int dp[MAXN];
int diameter = 0;

void dfs(int u, int parent) {
    dp[u] = 0;
    int max1 = 0, max2 = 0;  // 最长和次长路径
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        int len = dp[v] + 1;
        if (len > max1) {
            max2 = max1;
            max1 = len;
        } else if (len > max2) {
            max2 = len;
        }
    }
    
    dp[u] = max1;
    diameter = max(diameter, max1 + max2);
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    dfs(1, -1);
    cout << diameter << endl;
    
    return 0;
}

树的重心

问题描述：
找到树的重心（删除后使得各连通块大小最大值最小的节点）。

状态定义：

  • size[u] 表示以 为根的子树大小
  • maxPart[u] 表示删除 后最大连通块大小

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int n;
vector<int> tree[MAXN];
int size[MAXN];
int maxPart[MAXN];
int centroid = -1;
int minMaxPart = MAXN;

void dfs(int u, int parent) {
    size[u] = 1;
    maxPart[u] = 0;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        
        dfs(v, u);
        
        size[u] += size[v];
        maxPart[u] = max(maxPart[u], size[v]);
    }
    
    maxPart[u] = max(maxPart[u], n - size[u]);
    
    if (maxPart[u] < minMaxPart) {
        minMaxPart = maxPart[u];
        centroid = u;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    dfs(1, -1);
    cout << "树的重心: " << centroid << endl;
    cout << "最大连通块大小: " << minMaxPart << endl;
    
    return 0;
}

7️⃣ 轮廓线DP（插头DP）

核心思想： 处理平面或网格上的铺砖、回路等问题。

状态定义：

  • 用二进制表示轮廓线上每个格子的状态（是否有插头）

适用场景：

  • 棋盘覆盖问题
  • 哈密顿回路
  • 电路板布线

经典例题：多米诺骨牌铺砖

问题描述：
用 的骨牌铺满 的棋盘，求方案数。

代码实现（简化版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstring>
using namespace std;

const int MAXM = 12;
const int MOD = 1e9 + 7;
int n, m;
long long dp[2][1 << MAXM];

void solve() {
    memset(dp, 0, sizeof(dp));
    int cur = 0;
    dp[cur][0] = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int next = cur ^ 1;
            memset(dp[next], 0, sizeof(dp[next]));
            
            for (int state = 0; state < (1 << m); state++) {
                if (dp[cur][state] == 0) continue;
                
                // 当前位置已被占用
                if (state & (1 << j)) {
                    dp[next][state ^ (1 << j)] += dp[cur][state];
                    dp[next][state ^ (1 << j)] %= MOD;
                } else {
                    // 竖着放
                    if (i + 1 < n) {
                        dp[next][state | (1 << j)] += dp[cur][state];
                        dp[next][state | (1 << j)] %= MOD;
                    }
                    // 横着放
                    if (j + 1 < m && !(state & (1 << (j + 1)))) {
                        dp[next][state | (1 << (j + 1))] += dp[cur][state];
                        dp[next][state | (1 << (j + 1))] %= MOD;
                    }
                }
            }
            
            cur = next;
        }
    }
    
    cout << dp[cur][0] << endl;
}

int main() {
    cin >> n >> m;
    solve();
    return 0;
}

📊 DP优化技巧

1. 滚动数组优化空间

将二维 DP 优化为一维，节省空间。

1
2
3
4
5
6
7
8
9
10
11
// 优化前
int dp[MAXN][MAXM];

// 优化后
int dp[2][MAXM];  // 只保留当前行和上一行
int cur = 0;
for (int i = 0; i < n; i++) {
    int next = cur ^ 1;
    // ... 状态转移 ...
    cur = next;
}

2. 单调队列优化

适用于状态转移方程中有 或 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 维护区间最小值
deque<int> dq;
for (int j = 0; j < m; j++) {
    // 移除超出范围的元素
    while (!dq.empty() && dq.front() < j - k) {
        dq.pop_front();
    }
    // 移除不可能成为最小值的元素
    while (!dq.empty() && dp[dq.back()] >= dp[j]) {
        dq.pop_back();
    }
    dq.push_back(j);
    // 当前区间最小值
    ans[j] = dp[dq.front()];
}

3. 矩阵快速幂优化

适用于线性递推关系。

1
2
3
4
// 斐波那契数列
// F(n) = F(n-1) + F(n-2)
// 转化为矩阵乘法
// [F(n), F(n-1)] = [F(n-1), F(n-2)] * [[1, 1], [1, 0]]

🎯 刷题建议

入门题目

  1. [LeetCode 70] 爬楼梯
  2. [LeetCode 198] 打家劫舍
  3. [LeetCode 53] 最大子数组和
  4. [LeetCode 300] 最长递增子序列
  5. [LeetCode 322] 零钱兑换

进阶题目

  1. [LeetCode 416] 分割等和子集（0-1背包）
  2. [LeetCode 1143] 最长公共子序列
  3. [LeetCode 312] 戳气球（区间DP）
  4. [LeetCode 691] 贴纸拼词（状压DP）
  5. [LeetCode 337] 打家劫舍 III（树形DP）

高级题目

  1. [POJ 1185] 炮兵阵地（状压DP）
  2. [POJ 3254] Corn Fields（轮廓线DP）
  3. [HDU 1024] Max Sum Plus Plus
  4. [Codeforces] DP专题

💡 学习建议

  1. 理解本质：掌握DP的核心思想，而不是死记模板
  2. 状态设计：多练习如何设计状态，这是DP的关键
  3. 画图辅助：通过画图理解状态转移过程
  4. 从简单开始：先掌握线性DP和背包DP
  5. 总结规律：整理常见DP类型的套路和技巧
  6. 大量练习：DP需要大量练习才能熟练掌握

📚 参考资料

  • 《算法竞赛进阶指南》- 李煜东
  • 《算法导论》- CLRS
  • 《背包九讲》- 崔添翼
  • OI Wiki - 动态规划专题
  • Codeforces DP教程

💪 加油！ 动态规划是算法竞赛的核心内容，掌握好DP能够解决大量复杂问题。记住：多思考状态设计，多练习，多总结！

祝你在算法竞赛中取得优异成绩！🏆