TIP
DP 问题的本质：有限集中的最优解 DP 问题的时间复杂度分析方法：状态数量 * 转移计算量注意：方程中需要计算下标 i-1 的时候，输入需要从 1 开始，否则从 0 开始

表示集合及集合的状态
划分集合：寻找最后一个不同点
状态计算：把集合分成若干个子集，先求解若干个子集的解，再加起来
考虑状态转移：
- 先考虑：如果没有进行这个操作应该是什么状态
- 然后考虑：进行这一步操作之后会对你下一个状态造成什么影响
- 然后再加上之前状态表示中，决策出来的那个 DP 属性，写出状态转移方程
考虑状态数据的初始化

背包问题#

在二维优化到一维的过程中，如果二维的转移方程用到了上一次计算的数据，在优化到一维时，应该从大到小枚举，否则从小到大枚举。详见 01 背包的一维优化

01 背包#

有 N 件物品和一个容量是 V 的背包。每件物品最多只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

思路#

分析部分#

状态计算部分#

设状态 f(i, j) 代表前 i 个物品，背包容量 j 下的最大价值，以是否包含第 i 件物品，划分整个集合

状态转移方程及其优化#

朴素的状态转移方程（二维）#

f[i][j] = \begin{cases} f[i - 1][j] & \text{} v_i \geq j \\ \max\{f[i - 1][j], f[i - 1][j - v_i]\} + w_i & \text{} v_i < j \end{cases}

从计算公式可以看出，f[i][j] 是由 f[i - 1][j -vi] 和 w[i] 计算出来的。也就是 f[i][j] 的值是可以从前面已经计算出的 f 值求出来。如果我们能确定 f[i][j] 的一部分初始值，就能通过该公式，一步步计算得出 f[N][V]，也就是我们要找的答案。显然，初始值为 f[0][0~m] = 0

优化的状态转移方程（一维）#

如果空间压缩成一维，对于 01 背包问题，更新 f[i][j] 需要上一轮的 j - v[i]，对应的是 i-1

如果 j 从小到大遍历，由于先计算 j - v[i] 再计算 j，上一轮的值会被覆盖

代码#

写代码时，判断从 0 还是从 1 开始循环的方法：检查 f[i][j] 的合法性

1
// Problem: 01背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/2/
4
// Time: 2026-01-28 13:02:37
5
// 注意初始化时需要计算所有状态
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 1010;
10

11
int n, m;
12
int v[N], w[N];
13
int f[N][N];
14

15
int main()
16
{
17
    cin >> n >> m;
18

19
    for (int i = 1; i <= n; i++)
20
        cin >> v[i] >> w[i]; // 读入所有物品
21

22
    // 根据题意，f[0][0~m] = 0
23

24
    for (int i = 1; i <= n; i++)
25
    {
26
        for (int j = 0; j <= m; j++)
27
        {
28
            f[i][j] = f[i - 1][j]; // 左侧集合
29

30
            if (j >= v[i]) // 右侧集合
31
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
32
        }
33
    }
34

35
    cout << f[n][m] << endl;
36
    return 0;
37
}

1
// Problem: 01背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/2/
4
// Time: 2026-01-28 13:02:37
5
// 注意初始化时需要计算所有状态
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 1010;
10

11
int n, m;
12
int v[N], w[N];
13
int f[N];
14

15
int main()
16
{
17
    cin >> n >> m;
18

19
    for (int i = 1; i <= n; i++)
20
        cin >> v[i] >> w[i]; // 读入所有物品
21

22

23
    for (int i = 1; i <= n; i++)
24
        for (int j = m; j >= v[i]; j--)
25
            f[j] = max(f[j], f[j - v[i]] + w[i]);
26

27
    cout << f[m] << endl;
28
    return 0;
29
}

完全背包#

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

思路#

分析部分#

状态计算部分#

状态转移方程及其优化#

朴素的状态转移方程#

f[i][j] = \max\big( f[i][j],\; f[i-1][j - k \cdot v[i]] + k \cdot w[i] \big)

优化的状态转移方程#

把 k 展开，进行枚举：

\footnotesize f[i,j] = \max \scriptsize( f[i-1,j],\; f[i-1,j-v]+w,\; f[i-1,j-2v]+2w,\; f[i-1,j-3v]+3w,\; \dots \big)

\footnotesize f[i,j-v] = \max \footnotesize( f[i-1,j-v],\; f[i-1,j-2v]+w,\; f[i-1,j-3v]+2w,\; \dots \big)

也就是说，f[i][j] 最大值的时候，只需要将 f[i][j-v] 的最大值直接 +w 即可

由上两式，可得出如下递推关系：

f[i][j] = \max\big( f[i,j-v] + w,\; f[i-1][j] \big)

即有状态转移方程：

f[i][j] = \max\big( f[i][j],\; f[i][j - v[i]] + w[i] \big)

可以再变成更优化的状态转移方程（一维）：

f[j] = \max\big( f[j],\; f[j - v[i]] + w[i] \big)

注：对于完全背包，更新 f[i][j] 需要的是本轮的 j - v[i]，所以需要从小到大遍历

代码#

1
// Problem: 完全背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/3/
4
// Time: 2026-01-29 14:41:38
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9

10
const int N = 1010;
11

12
int n, m;
13
int v[N], w[N];
14
int f[N][N];
15

16
int main()
17
{
18
    cin >> n >> m;
19
    for (int i = 1; i <= n; i++)
20
        cin >> v[i] >> w[i];
21

22
    for (int i = 1; i <= n; i++)
23
        for (int j = 0; j <= m; j++)
24
            for (int k = 0; k * v[i] <= j; k++) // 注意k的大小受体积j的约束
25
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i]);
26

27
    cout << f[n][m] << endl;
28
    return 0;
29
}

1
// Problem: 完全背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/3/
4
// Time: 2026-01-29 14:41:38
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9

10
const int N = 1010;
11

12
int n, m;
13
int v[N], w[N];
14
int f[N][N];
15

16
int main()
17
{
18
    cin >> n >> m;
19
    for (int i = 1; i <= n; i++)
20
        cin >> v[i] >> w[i];
21

22
    for (int i = 1; i <= n; i++)
23
        for (int j = 0; j <= m; j++)
24
        {
25
            f[i][j] = f[i - 1][j];
26

27
            if (j >= v[i])
28
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
29
        }
30

31
    cout << f[n][m] << endl;
32
    return 0;
33
}

1
// Problem: 完全背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/3/
4
// Time: 2026-01-29 14:41:38
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9

10
const int N = 1010;
11

12
int n, m;
13
int v[N], w[N];
14
int f[N];
15

16
int main()
17
{
18
    cin >> n >> m;
19
    for (int i = 1; i <= n; i++)
20
        cin >> v[i] >> w[i];
21

22
    for (int i = 1; i <= n; i++)
23
        for (int j = v[i]; j <= m; j++)
24
        {
25
            f[j] = max(f[j], f[j - v[i]] + w[i]);
26
        }
27

28
    cout << f[m] << endl;
29
    return 0;
30
}

多重背包#

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 完全背包只有背包体积够不够用，而多重背包既要考虑背包体积，又要考虑背包体积够了，但物品数量不够的情况

思路#

分析部分#

状态计算部分#

和完全背包问题高度相似，只是把“完全”的条件改了一下

状态转移方程及其优化#

朴素的状态转移方程#

注意枚举 k 的时候有以下限制：k <= s[i] && k * v[i] <= j

f[i][j] = \max\big( f[i][j],\; f[i-1][j - k \cdot v[i]] + k \cdot w[i] \big)

优化技巧：二进制分组优化 +01 背包一维优化#

存在如下定理：任意一个实数都可以用二进制数来表示

二进制优化是一种减少枚举次数的策略：

假如要拿 1001 次苹果，暴力枚举方式就是拿 1001 次，而二进制优化的思维是把 1001 个苹果分成装有 512,256,128,64,32,8,1 的七个箱子，这样一来，1001 次操作就变成了 7 次操作。时间复杂度由 $O(n^3)$ 变为了 $O(n^2 \log S)$

二进制优化后，多重背包就转换成了一个 01 背包问题，也就是对于每一堆，我们都尝试取或不取两种情况，其实等价于枚举 1001 次，因为 DP 问题只考虑最优解，通过这种方法，大大减小了计算的次数

代码#

1
// Problem: 多重背包问题 I
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/4/
4
// Time: 2026-01-29 20:37:20
5
// 数据范围比较小，直接打暴力即可
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <iostream>
8
using namespace std;
9
const int N = 110;
10

11
int n, m;
12
int v[N], w[N], s[N];
13
int f[N][N];
14

15
int main()
16
{
17
    cin >> n >> m;
18

19
    for (int i = 1; i <= n; i++)
20
        cin >> v[i] >> w[i] >> s[i];
21

22
    for (int i = 1; i <= n; i++)
23
        for (int j = 0; j <= m; j++)
24
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
25
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
26

27
    cout << f[n][m] << endl;
28
    return 0;
29
}

1
// Problem: 多重背包问题 II
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/5/
4
// Time: 2026-01-31 09:13:09
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9

10
const int N = 25000, M = 2010;
11

12
int n, m;
13
int v[N], w[N];
14
int f[N];
15

16
int main()
17
{
18
    cin >> n >> m;
19

20
    int cnt = 0; // 分组的组别
21
    for (int i = 1; i <= n; i++) // n种物品，对于每一种物品，我们都要把它二进制分堆
22
    {
23
        int a, b, s;
24
        cin >> a >> b >> s;
25

26
        int k = 1; // 组别里面的个数，从1也就是2的0次方开始
27
        while (k <= s)
28
        {
29
            cnt++; // 增加组别数
30
            v[cnt] = a * k; // 整体的体积
31
            w[cnt] = b * k; // 整体的价值
32
            s -= k; // s减小
33
            k *= 2; // 组别里的个数增加（乘2）
34
        }
35

36
        if (s > 0) // 二进制分完后，剩下的那一组
37
        {
38
            cnt++;
39
            v[cnt] = a * s;
40
            w[cnt] = b * s;
41
        }
42
    }
43

44
    n = cnt; // 枚举的次数从原来的个数，变为组别数
45

46
    // 01背包的一维做法
47
    for (int i = 1; i <= n; i++)
48
        for (int j = m; j >= v[i]; j--)
49
            f[j] = max(f[j], f[j - v[i]] + w[i]);
50

51
    cout << f[m] << endl;
52
    return 0;
53
}

分组背包#

有 N 组物品和一个容量是 V 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

思路#

分析部分#

状态计算部分#

分组背包问题，是枚举第 i 组物品中选哪个（或不选）

状态转移方程及其优化#

朴素的状态转移方程#

f[i][j] = \begin{cases} f[i - 1][j] & \text{} v[i][k] > j \\ \max\{f[i][j], f[i - 1][j - v[i][k]] + w[i][k] & \text{} v[i][k] \leqslant j \end{cases}

一维优化的状态转移方程#

注意体积 j 需要从大到小枚举

f[j] = \max\big( f[j],\; f[j - v[i][k]] + w[i][k] \big) \quad v[i][k] \leq j

代码#

1
// Problem: 分组背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/9/
4
// Time: 2026-01-31 11:03:12
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <algorithm>
8
#include <iostream>
9
using namespace std;
10

11
const int N = 110;
12

13
int n, m;
14
int v[N][N], w[N][N], s[N];
15
int f[N][N];
16

17
int main()
18
{
19
    cin >> n >> m;
20

21
    for (int i = 1; i <= n; i++)
22
    {
23
        cin >> s[i];
24
        for (int j = 0; j < s[i]; j++)
25
            cin >> v[i][j] >> w[i][j];
26
    }
27

28
    for (int i = 1; i <= n; i++)
29
    {
30
        for (int j = 0; j <= m; j++)
31
        {
32
            f[i][j] = f[i - 1][j]; // 不选
33
            for (int k = 0; k < s[i]; k++)
34
            {
35
                if (j >= v[i][k])
36
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
37
            }
38
        }
39
    }
40
    cout << f[n][m] << endl;
41
    return 0;
42
}

1
// Problem: 分组背包问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/9/
4
// Time: 2026-01-31 11:03:12
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <algorithm>
8
#include <iostream>
9
using namespace std;
10

11
const int N = 110;
12

13
int n, m;
14
int v[N][N], w[N][N], s[N];
15
int f[N];
16

17
int main()
18
{
19
    cin >> n >> m;
20

21
    for (int i = 1; i <= n; i++)
22
    {
23
        cin >> s[i];
24
        for (int j = 0; j < s[i]; j++)
25
            cin >> v[i][j] >> w[i][j];
26
    }
27

28
    for (int i = 1; i <= n; i++)
29
        for (int j = m; j >= 0; j--)
30
            for (int k = 0; k < s[i]; k++)
31
                if (v[i][k] <= j)
32
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
33

34
    cout << f[m] << endl;
35
    return 0;
36
}

线性 DP#

此类问题的递推方程存在一个线性关系。可能是一维线性，也可能是多维线性，求解问题时，有一个“线性”的顺序

数字三角形#

思路#

分析部分#

状态转移方程#

f[i][j] = \max\big( f[i - 1][j - 1] + a[i][j],\; f[i - 1][j] + a[i][j] \big)

代码#

注意：由于状态转移方程中的 max，为了规避边界问题，我们把所有的边界都设置成负无穷在初始化 f[][] 为负无穷时，第二维应当初始化到 j+1

1
// Problem: 数字三角形
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/900/
4
// Time: 2026-01-31 20:51:31
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 510, INF = 0x3f3f3f3f;
10

11
int n;
12
int a[N][N];
13
int f[N][N];
14

15
int main()
16
{
17
    cin >> n;
18
    for (int i = 1; i <= n; i++)
19
        for (int j = 1; j <= i; j++)
20
            cin >> a[i][j];
21

22
    for (int i = 0; i <= n; i++)
23
        for (int j = 0; j <= i + 1; j++)
24
            f[i][j] = -INF; // 初始化成负无穷，规避max带来的边界问题
25

26
    f[1][1] = a[1][1];
27

28
    for (int i = 2; i <= n; i++)
29
        for (int j = 1; j <= i; j++)
30
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
31

32
    int res = -INF; // 遍历尾部的点时，可能会出现到不了的情况，所以初始化成负无穷
33
    for (int i = 1; i <= n; i++) // 遍历三角形最后一行
34
        res = max(res, f[n][i]);
35

36
    cout << res << endl;
37
    return 0;
38
}

最长上升子序列#

思路（动态规划）#

分析部分#

状态转移方程#

时间复杂度 $O(n^2)$

f[i] = \max\big( f[i],\; f[j] + 1 \big), \quad \text{} a[i] > a[j]

思路（贪心 + 二分）#

https://www.acwing.com/solution/content/6525/ 适用于数据范围比较大的情况，由于动态规划比较暴力，会 TLE

代码#

1
// Problem: 最长上升子序列
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/897/
4
// Time: 2026-02-01 10:51:11
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 1010;
10

11
int n;
12
int a[N], f[N];
13

14
int main()
15
{
16
    cin >> n;
17
    for (int i = 1; i <= n; i++)
18
        cin >> a[i];
19

20
    for (int i = 1; i <= n; i++)
21
    {
22
        f[i] = 1; // 初始化只有a[i]一个数的情况
23

24
        for (int j = 1; j <= i; j++) // 从1开始枚举，第i个数的上一个数是哪个数
25
        {
26
            if (a[i] > a[j]) // 如果a[i]更大，显然是上升的
27
                f[i] = max(f[i], f[j] + 1);
28
        }
29
    }
30

31
    int res = 0;
32
    for (int i = 1; i <= n; i++) // 遍历所有的“第i个点”
33
        res = max(res, f[i]);
34

35
    cout << res << endl;
36
    return 0;
37
}

1
// Problem: 最长上升子序列 II
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/898/
4
// Time: 2026-02-02 13:22:39
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 100010;
10

11
int n;
12
int a[N];
13
int q[N]; // 存储长度为i的上升子序列中末尾元素最小的数
14

15
int main()
16
{
17
    cin >> n;
18

19
    for (int i = 0; i < n; i++)
20
        cin >> a[i];
21

22
    int len = 0; // 记录q数组元素个数
23

24
    for (int i = 0; i < n; i++)
25
    {
26
        int l = 0, r = len;
27
        while (l < r)
28
        {
29
            int mid = l + r + 1 >> 1;
30
            if (q[mid] < a[i])
31
                l = mid;
32
            else
33
                r = mid - 1;
34
        }
35

36
        q[r + 1] = a[i];
37
        if (r + 1 > len)
38
            len++;
39
    }
40

41
    cout << len << endl;
42
    return 0;
43
}

最长公共子序列#

思路#

代码#

1
// Problem: 最长公共子序列
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/899/
4
// Time: 2026-02-01 15:52:03
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 1010;
10

11
int f[N][N];
12
char a[N], b[N];
13
int n, m;
14

15
int main()
16
{
17
    cin >> n >> m >> a + 1 >> b + 1;
18
    for (int i = 1; i <= n; i++)
19
        for (int j = 1; j <= m; j++)
20
        {
21
            if (a[i] == b[j])
22
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
23
            else
24
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
25
        }
26

27
    cout << f[n][m] << endl;
28
    return 0;
29
}

编辑距离#

思路#

代码#

1
// Problem: 最短编辑距离
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/904/
4
// Time: 2026-02-01 17:27:13
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 1010;
9

10
int n, m;
11
char a[N], b[N];
12
int f[N][N];
13

14
int main()
15
{
16
    cin >> n >> a + 1 >> m >> b + 1;
17

18
    // 初始化
19
    for (int i = 0; i <= m; i++)
20
        f[0][i] = i;
21
    for (int i = 0; i <= n; i++)
22
        f[i][0] = i;
23

24
    for (int i = 1; i <= n; i++)
25
        for (int j = 1; j <= m; j++)
26
        {
27
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
28
            if (a[i] == b[j])
29
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
30
            else
31
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
32
        }
33

34
    cout << f[n][m] << endl;
35
    return 0;
36
}

1
// Problem: 编辑距离
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/901/
4
// Time: 2026-02-02 10:03:54
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 15, M = 1010;
9

10
int n, m;
11
int f[N][N];
12
char str[M][N];
13

14
int edit_distance(char a[], char b[])
15
{
16
    int la = strlen(a + 1), lb = strlen(b + 1);
17

18
    for (int i = 0; i <= lb; i++)
19
        f[0][i] = i;
20
    for (int i = 0; i <= la; i++)
21
        f[i][0] = i;
22

23
    for (int i = 1; i <= la; i++)
24
        for (int j = 1; j <= lb; j++)
25
        {
26
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
27
            if (a[i] == b[j])
28
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
29
            else
30
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
31
        }
32

33
    return f[la][lb];
34
}
35
int main()
36
{
37
    cin >> n >> m;
38
    for (int i = 0; i < n; i++)
39
        cin >> str[i] + 1;
40

41
    while (m--)
42
    {
43
        char s[N];
44
        int limit;
45
        cin >> s + 1 >> limit;
46

47
        int res = 0;
48
        for (int i = 0; i < n; i++)
49
            if (edit_distance(str[i], s) <= limit)
50
                res++;
51

52
        cout << res << endl;
53
    }
54
    return 0;
55
}

区间 DP#

所有的区间 dp 问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 通过计算获得，j = i + len - 1），最后枚举分割点，构造状态转移方程

例题：石子合并#

思路#

代码#

1
// Problem: 石子合并
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/284/
4
// Time: 2026-02-02 10:16:14
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 310;
9

10
int n;
11
int s[N]; // 前缀和
12
int f[N][N]; // 表示将i到j这一段石子合并成一堆的方案的集合，属性 Min
13

14
int main()
15
{
16
    cin >> n;
17
    for (int i = 1; i <= n; i++)
18
    {
19
        cin >> s[i];
20
        s[i] += s[i - 1];
21
    }
22

23
    memset(f, 0x3f, sizeof f); // 初始化成无穷大
24

25
    for (int len = 1; len <= n; len++) // 从小到大枚举长度
26
        for (int i = 1; i + len - 1 <= n; i++) // 枚举区间左端点
27
        {
28
            int l = i;
29
            int r = l + len - 1; // 计算区间右端点
30
            if (len == 1) // 合并一堆石子的代价为0
31
            {
32
                f[l][r] = 0;
33
                continue;
34
            }
35

36
            for (int k = l; k <= r - 1; k++) // 枚举分界点
37
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
38
        }
39

40
    cout << f[1][n] << endl;
41
    return 0;
42
}

计数类 DP#

例题：整数划分#

一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。我们将这样的一种表示称为正整数 n 的一种划分。现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

思路#

代码#

1
// Problem: 整数划分
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/902/
4
// Time: 2026-02-02 21:09:58
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 1010, mod = 1e9 + 7;
10

11
int n;
12
int f[N];
13

14
int main()
15
{
16
    cin >> n;
17
    f[0] = 1; // 除f[0]之外其余都是0
18

19
    for (int i = 1; i <= n; i++)
20
        for (int j = i; j <= n; j++)
21
            f[j] = (f[j] + f[j - i]) % mod;
22

23
    cout << f[n] << endl;
24
    return 0;
25
}

1
// Problem: 整数划分
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/902/
4
// Time: 2026-02-02 21:09:58
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 1010, mod = 1e9 + 7;
10

11
int n;
12
int f[N][N];
13

14
int main()
15
{
16
    cin >> n;
17
    f[0][0] = 1; // 除f[0]之外其余都是0
18

19
    for (int i = 1; i <= n; i++)
20
        for (int j = 1; j <= i; j++)
21
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
22

23
    int res = 0;
24
    for (int i = 1; i <= n; i++)
25
        res = (res + f[n][i]) % mod;
26

27
    cout << res << endl;
28
    return 0;
29
}

数位统计 DP#

例题：数位统计#

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下： 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等…

思路#

代码#

1
// Problem: 计数问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/340/
4
// Time: 2026-02-03 21:58:49
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8

9
int get(vector<int> num, int l, int r) // 求num里第l位到第r位的数字
10
{
11
    int res = 0;
12
    for (int i = l; i >= r; i--)
13
        res = res * 10 + num[i];
14

15
    return res;
16
}
17

18
int power10(int x) // 求10的i次方
19
{
20
    int res = 1;
21
    while (x--)
22
        res *= 10;
23
    return res;
24
}
25

26
int count(int n, int x)
27
{
28
    if (n == 0)
29
        return 0;
30

31
    vector<int> num; // 存储数字n的每位数（倒着放进vector）
32
    while (n)
33
    {
34
        num.push_back(n % 10);
35
        n /= 10;
36
    }
37

38
    n = num.size(); // 把每位数都放进vector以后，n可以表示数的长度
39

40
    int res = 0; // 答案（出现次数）
41
    for (int i = n - 1 - !x; i >= 0; i--) // 从num的最高位开始枚举（把数字正过来）
42
    {
43
        if (i < n - 1)
44
        {
45
            res += get(num, n - 1, i + 1) * power10(i);
46
            if (x == 0)
47
                res -= power10(i); // 不能出现前导0，减掉一个power10
48
        }
49

50
        if (num[i] == x)
51
            res += get(num, i - 1, 0) + 1;
52

53
        else if (num[i] > x)
54
            res += power10(i);
55
    }
56

57
    return res;
58
}
59
int main()
60
{
61
    int a, b;
62
    while (cin >> a >> b, a || b)
63
    {
64
        if (a > b)
65
            swap(a, b);
66

67
        // 分别统计从0到9的次数
68
        for (int i = 0; i < 10; i++)
69
            cout << count(b, i) - count(a - 1, i) << " ";
70

71
        cout << endl;
72
    }
73

74
    return 0;
75
}

状压 DP#

状压 DP 是动态规划的一种，通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的．为了达到更低的时间复杂度，通常需要寻找更低状态数的状态．大部分题目中会利用二元状态，用 n 位二进制数表示 n 个独立二元状态的情况．状压 DP 的时间复杂度为 $O(n^22^n)$ ，通常可以过 $n \leqslant 21$ 的数据范围

例题：蒙德里安的梦想#

求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。

思路#

代码#

1
// Problem: 蒙德里安的梦想
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/293/
4
// Time: 2026-02-06 09:12:12
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 12, M = 1 << N; // 2^12
9

10
int n, m;
11
long long f[N][M];
12
vector<vector<int>> state(M); // 预处理出所有合法状态
13
bool st[M]; // 判断当前这一列是不是可以被竖着的方格填满
14

15
int main()
16
{
17
    while (cin >> n >> m, n || m)
18
    {
19
        for (int i = 0; i < (1 << n); i++) // 预处理st数组
20
        {
21
            int cnt = 0; // 表示0的个数
22
            bool is_valid = true;
23

24
            for (int j = 0; j < n; j++)
25
            {
26
                if ((i >> j) & 1)
27
                // i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位；
28
                //  &1为判断该位是否为1，如果为1进入if
29
                {
30
                    if (cnt & 1) // 这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
31
                    {
32
                        is_valid = false;
33
                        break;
34
                    }
35
                    cnt = 0;
36
                    // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
37
                }
38
                else
39
                    cnt++;
40
            }
41

42
            if (cnt & 1) // 判断连续个0的个数，如果是奇数就是false
43
                is_valid = false;
44

45
            st[i] = is_valid;
46
        }
47

48
        // 第二部分：预处理2
49
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
50
        // 下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
51
        for (int j = 0; j < (1 << n); j++) // 枚举所有合法状态
52
        {
53
            state[j].clear();
54
            for (int k = 0; k < (1 << n); k++)
55
                if ((j & k) == 0 && st[j | k])
56
                    // j|k是考虑第i-1列到底有几个1，包含了第i-2列伸过来和第i-1列伸出去的两种情况
57
                    state[j].push_back(k);
58
        }
59

60

61
        // 第三部分：开始dp
62
        memset(f, 0, sizeof f);
63
        f[0][0] = 1;
64

65
        for (int i = 1; i <= m; i++) // 遍历每一列
66
        {
67
            for (int j = 0; j < (1 << n); j++) // 遍历当前列（第i列）的所有状态j
68
            {
69
                for (auto k: state[j]) // 遍历第i-1列的状态k
70
                {
71
                    f[i][j] += f[i - 1][k];
72
                }
73
            }
74
        }
75

76
        cout << f[m][0] << endl;
77
    }
78

79
    return 0;
80
}

例题：最短 Hamilton 路径（旅行商问题）#

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

思路#

代码#

1
// Problem: 最短Hamilton路径
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/93/
4
// Time: 2026-02-06 10:44:06
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 20, M = 1 << 20;
9

10
int n;
11
int f[M][N]; // M代表状态
12
int w[N][N]; // 边权
13

14
int main()
15
{
16
    cin >> n;
17
    for (int i = 0; i < n; i++)
18
        for (int j = 0; j < n; j++)
19
            cin >> w[i][j];
20

21
    memset(f, 0x3f, sizeof f);
22
    f[1][0] = 0;
23

24
    for (int i = 0; i < (1 << n); i++)
25
        for (int j = 0; j < n; j++)
26
            if (i >> j & 1)
27
                for (int k = 0; k < n; k++)
28
                    if ((i - (1 << j)) >> k & 1)
29
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
30

31
    cout << f[(1 << n) - 1][n - 1] << endl;
32
    return 0;
33
}

树形 DP#

例题：没有上司的舞会#

Ural 大学有 N 名职员，编号为 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 Hi 给出，其中 1 ≤ i ≤ N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

思路#

代码#

1
// Problem: 没有上司的舞会
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/287/
4
// Time: 2026-02-03 17:49:16
5
// 时间复杂度O(n)，n-1条边
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 6010;
10

11
int n;
12
int happy[N];
13
int h[N], e[N], ne[N], idx; // 邻接表
14
int f[N][2]; // 状态
15
bool has_father[N]; // 需要自己找根节点，即判断有没有父亲
16

17
void add(int a, int b)
18
{
19
    e[idx] = b;
20
    ne[idx] = h[a];
21
    h[a] = idx++;
22
}
23

24
void dfs(int u)
25
{
26
    f[u][1] = happy[u]; // 递归到第u层，就先把选上的情况赋值
27

28
    for (int i = h[u]; i != -1; i = ne[i])
29
    {
30
        int j = e[i];
31
        dfs(j); // 递归处理
32

33
        f[u][0] += max(f[j][0], f[j][1]);
34
        f[u][1] += f[j][0];
35
    }
36
}
37

38
int main()
39
{
40
    cin >> n;
41
    for (int i = 1; i <= n; i++)
42
        cin >> happy[i];
43

44
    memset(h, -1, sizeof h);
45

46
    for (int i = 0; i < n - 1; i++)
47
    {
48
        int a, b;
49
        cin >> a >> b;
50
        has_father[a] = true;
51
        add(b, a);
52
    }
53

54
    int root = 1;
55
    while (has_father[root])
56
        root++;
57

58
    dfs(root); // 从根节点开始搜索
59

60
    cout << max(f[root][0], f[root][1]); // 输出不选根节点和选根节点的最大值
61

62
    return 0;
63
}

记忆化搜索#

基本思想#

记忆化搜索就是 dfs+ 记忆化数组 f[i][j]。

先初始化整个 f[][] 为 -1，在算某一个位置时，把它的所有路径上所有算过的位置状态保存在数组 f[i][j] 里。if (f[x][y] != -1) return f[x][y];，下次求某个被算过的位置的状态时，无需重新计算，直接返回。是数组 f[i][j] 起到了记忆的作用。

例题：滑雪#

思路#

代码#

1
// Problem: 滑雪
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/903/
4
// Time: 2026-02-03 20:46:34
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 310;
9

10
int n, m;
11
int h[N][N]; // 高度
12
int f[N][N]; // 状态
13

14
int dx[4] = {-1, 0, 1, 0};
15
int dy[4] = {0, -1, 0, 1};
16

17
int dp(int x, int y)
18
{
19
    int &v = f[x][y]; // 取引用简化代码
20

21
    if (v != -1) // 如果这个状态已经算过了，就直接return回去
22
        return v;
23

24
    v = 1; // 初始化v，假如在原地不动，走不了，路径就是1
25

26
    for (int i = 0; i < 4; i++)
27
    {
28
        int a = x + dx[i], b = y + dy[i];
29

30
        // 满足这些条件，才能从(x, y)走到(a, b)
31
        if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
32
            v = max(v, dp(a, b) + 1); // 记忆化搜索
33
    }
34

35
    return v;
36
}
37
int main()
38
{
39
    cin >> n >> m;
40

41
    for (int i = 1; i <= n; i++)
42
        for (int j = 1; j <= n; j++)
43
            cin >> h[i][j];
44

45
    memset(f, -1, sizeof f);
46

47
    int res = 0;
48

49
    // 枚举滑雪场里的每个点作为起点
50
    for (int i = 1; i <= n; i++)
51
        for (int j = 1; j <= m; j++)
52
            res = max(res, dp(i, j));
53

54
    cout << res << endl;
55
    return 0;
56
}