背包问题

01背包问题

题干

有 件物品和一个容量是 的背包。每件物品只能使用一次。

第 件物品的体积是 ，价值是 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，，，用空格隔开，分别表示物品数量和背包容积。

接下来有 行，每行两个整数 ，用空格隔开，分别表示第 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围


输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

思路分析

主要考虑两方面：状态表示和状态计算。

状态表示：在本题中，有两个变量：给定的物品和背包容量。如果这两个变量已知，那么一定会有一个确定的属性；这个属性在本题中就是背包物品价值的最大值。因此我们要根据给定的物品和背包容量，得到背包物品价值最大值的动态规划。对于这两个变量，为了方便划分，我们可以规定 表示只用前个物品，体积不超过的背包物品价值的最大值。我们的集合就是所有只从前个物品中选，并且总体积不超过的选法，维护的集合属性就是价值的最大值。

状态计算：本质上就是集合划分，我们要根据已有的数据，通过表达式得到当前数据。

回忆学习组合数时： 表示从n个数中选出m个数，可以分成两种选法：包含一个数k，此时还有种选法；或者不包含k，此时还有种选法；因此得到

这里我们也可以使用类似的方法：对于，分成两种：如果我没有用第个物品，此时价值最大值为；如果我用了第个物品，此时价值最大值为；与上式不同的地方在于，此处维护的是最大值而不是方法数量，因此可以得到

注意：是一定存在的，因为是从1开始的；而不一定存在，因为可能小于，要写个判断。

因此，我们可以建立一个数组，此题、数据范围都在以内，因此令，建立数组，将所有状态存起来；显然​均为0，由于开在全局数组就不用改了；代码完成如下：

版本1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;

int v[MAX], w[MAX], f[MAX][MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= V; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[N][V];
    return 0;
}

我们注意到，实际上对于每一个，该轮的所有仅与上一轮有关，并且我们并不需要所有的结果而是只需要​；因此可以开一个一维数组，实时更新每轮，我们可以直接把原代码数组的第一维去掉。

版本2

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 <bits/stdc++.h>
using namespace std;
const int MAX = 1010;

int v[MAX], w[MAX], f[MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= N; i++)
        /*
        for (int j = 0; j <= V; j++)
        {
            f[i][j] = f[i - 1][j]; 
            将第一维删去，变成 f[j] = f[j]，没有意义，这句可以直接删去
            
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            此处如果 j < v[i] ，会直接变成无意义循环，因此可以将循环设置成从 j = v[i] 开始并去掉判断
    		
    		注意：去掉第一维后变为 f[j] = max(f[j], f[j - v[i]] + w[i])
    		而原来是 f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
    		这两个并不等价；问题在于：修改后由于 j - v[i] 必然小于 j，那么f[j - v[i]]的更新会早于f[j]，
    		因此此处的 f[i - v[i]] 相当于之前的 f[i][j - v[i]] 而非 f[i - 1][j - v[i]]；
    		要解决这个问题，只需将数组从后往前更新即可。
        }
        */
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[V];
    return 0;
}

完全背包问题

题干

有 件物品和一个容量是 的背包。每件物品都有无限件可用。

第 件物品的体积是 ，价值是 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，，，用空格隔开，分别表示物品数量和背包容积。

接下来有 行，每行两个整数 ，用空格隔开，分别表示第 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围


输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
10

思路分析

按照01背包的思路，可以将分为有、、、个物品的情况，其中​​，即

注意到其实就是，也就是说
，
此时已经可以写代码了。

版本1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;

int v[MAX];
int w[MAX];
int f[MAX][MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= V; j++)
            for (int k = 0; j - k * v[i] >= 0; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[N][V];
    return 0;
}

不过这个代码是接近的复杂度，提交后发现果然，必须再想办法优化。

注意到

用代替，有

我们惊奇地发现，地表达式只比前者少了一项，且后面所有元素少了，因此有

有了这个结论，我们就可以将的复杂度简化为​的复杂度。

注意：与01背包类似，此处可能越界，因此要判断一下。

版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;

int v[MAX];
int w[MAX];
int f[MAX][MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= V; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) 
                f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
        }
    cout << f[N][V];
    return 0;
}

提交后发现轻松。但是观察01背包和完全背包，核心代码只不过是和的区别。也就是说，其实完全背包也可以简化成一维数组。

仿照01背包的思路，我们发现他们最大的不同之处在于：完全背包使用的是本轮的对应的，而01背包使用的是上轮的对应的​；由于01背包需要上轮的数据，因此我们选择从后往前遍历；而完全背包需要本轮的数据，我们直接从前往后遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;

int v[MAX], w[MAX], f[MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i];
    
        
    for (int i = 1; i <= N; i++)
        for (int j = v[i]; j <= V; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[V];
    return 0;
}

完全不同的两道题，在代码实现上居然只有前后遍历顺序的差距！

多重背包问题 I

题干

有 件物品和一个容量是 的背包。

第 件物品最多有件，每件体积是 ，价值是 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，，，用空格隔开，分别表示物品数量和背包容积。

接下来有 行，每行两个整数 用空格隔开，分别表示第 件物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围


输入样例

1
2
3
4
5
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

1
10

思路分析

第一反应是按照完全背包的思路，只不过此时物品数量有个固定的上限；只需要对第个物品数量循环遍历即可，时间复杂度，此题数据范围较小不会。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;

int v[MAX];
int w[MAX];
int s[MAX];
int f[MAX][MAX];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= V; j++)
            for (int k = 0; j - k * v[i] >= 0 && k <= s[i]; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[N][V];
    return 0;
}

多重背包问题 II

题干

有 件物品和一个容量是 的背包。

第 件物品最多有件，每件体积是 ，价值是 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，，，用空格隔开，分别表示物品数量和背包容积。

接下来有 行，每行两个整数 用空格隔开，分别表示第 件物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

​

输入样例

1
2
3
4
5
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

1
10

思路分析

显然上一题方法会，考虑简化。

思考：如果我们有1000个数，我们如何用最少的数字就可以表示出所有的数？计算机的底层逻辑已经给出了答案：二进制。我们可以将每个物品打包成一块，然后用打包后的物品做新的背包问题。最大值为1000，而已经可以表示所有1000以内的数，也就是说可以把1000个物品压缩成10个物品处理。

如果物品数量不是2的次方数-1，可以最后剩下的部分单独打包；每读入一种物品，就将这种物品全部打包存入数组。同时由于数组太大，开不下二维数组，因此只能开一维；我们要注意用的是哪一轮的数据，显然此题简化后是01背包的模板，用的是上一轮的数据，也就是说遍历体积时要倒序遍历。

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
#include <bits/stdc++.h>
using namespace std;
const int MAX = 12000;

int v[MAX];
int w[MAX];
int s[MAX];
int f[MAX];
int cnt;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
    {
        int vv, ww, ss, k = 1;
        cin >> vv >> ww >> ss;
        while (ss >= k)
        {
            cnt++;
            v[cnt] = vv * k;
            w[cnt] = ww * k;
            ss -= k;
            k *= 2;
        }
        if (ss)
        {
            cnt++;
            v[cnt] = vv * ss;
            w[cnt] = ww * ss;
        }
    }
    N = cnt;
    for (int i = 1; i <= N; i++)
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[V];
    return 0;
}

分组背包问题

题干

有 组物品和一个容量是 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 ，价值是 ，其中 是组号， 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 ，，用空格隔开，分别表示物品组数和背包容量。

接下来有 组数据：

  • 每组数据第一行有一个整数 ，表示第 个物品组的物品数量；
  • 每组数据接下来有 行，每行有两个整数 ，，用空格隔开，分别表示第 个物品组的第 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围



输入样例

1
2
3
4
5
6
7
8
3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

1
8

思路分析

与多重背包类似，直接遍历每一组的元素，找到每一组最大值即可。注意仍然是01背包变种，倒序遍历体积。

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
#include <bits/stdc++.h>
using namespace std;
const int MAX = 110;

int v[MAX][MAX];
int w[MAX][MAX];
int s[MAX];
int f[MAX];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= N; i++)
        for (int j = V; j >= 0; j--)
            for (int k = 1; k <= s[i]; k++)
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[V];
    return 0;
}

线性DP

数字三角形

题干

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

1
2
3
4
5
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 ，表示数字三角形的层数。

接下来 行，每行包含若干整数，其中第 行表示数字三角形第 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围


三角形中的整数

输入样例：

1
2
3
4
5
6
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

1
30

思路分析

我们只需要每次读入一个数时，自动将他计算成从三角形顶走到他的最大值即可；显然有公式

由于我们是从下标1开始存，因此不存在数组越界导致段错误的问题；只是此处我们使用了函数，如果未定义的地方为0而要经历的数字为负数就会出问题，因此可以把数组初始化成一个很小的数。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 1e9;

int a[N][N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            a[i][j] = -INF;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
        {
            cin >> a[i][j];
            a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
        }
    int res = -INF;
    for (int i = 1; i <= n; i++)
        res = max(res, a[n][i]);
    cout << res;
    return 0;
}

最长上升子序列 I

题干

给定一个长度为 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 。

第二行包含 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围


数列中的数

输入样例：

1
2
7
3 1 2 1 8 5 6

输出样例：

1
4

思路分析

直接使用线性，对数组的每一个数遍历其前方的每一个数，如果比前面的数更大就取长度大者，即
对于满足且的，

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int a[N], f[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[i] = 1;
    }
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(f[i], res);
    cout << res;
    return 0;
}

最长上升子序列 II

题干

给定一个长度为 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 。

第二行包含 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围


数列中的数

输入样例：

1
2
7
3 1 2 1 8 5 6

输出样例：

1
4

思路分析

显然上一个算法过不了。原因是对于每一个元素，如果遍历前面所有的元素，会造成许多浪费。怎样快速找到有用的那个（也就是可以接到尾巴的那个）？

先思考一个事实：对于一个函数，表示对于长度为的子序列末尾值的最小值，那么必然严格单调递增。

反证法：如果存在使得，那么这串长为的子序列的第个元素必然小于，这与是长度为的子序列末尾值最小值矛盾，因此必然严格单调递增。

这个结论有什么用？例如一个序列，显然有(除了)，以及；此时如果新来一个元素6，那么显然6无法接到7的后面，因此也接不到7后面的元素后面；而如果他接到4后面，又不如长度为5、结尾为5的序列，因此这个数应该接到从左到右大于等于它的第一个后面。这部分可以使用二分查找，实现。

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 <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e9;

int a[N], len[N];
// len[i] 表示长度为i的上升子序列的最小尾元素
int idx;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    len[++idx] = a[1];
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > len[idx])
            len[++idx] = a[i];
        else
        {
            int pos = lower_bound(len + 1, len + 1 + idx, a[i]) - len;
            // 找到 >= x 的第一个i，并将 len[i] 替换为x
            // 替换原理：len[i] >= x，且len[i-1] < x，那么将x接到len[i-1]后形成的长度为i的序列结尾更小
            len[pos] = a[i];
        }
    }
    cout << idx;
    return 0;
}

最长公共子序列

题干

给定两个长度分别为 和 的字符串 和 ，求既是 的子序列又是 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 和 。

第二行包含一个长度为 的字符串，表示字符串 。

第三行包含一个长度为 的字符串，表示字符串 。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

输入样例：

1
2
3
4 5
acbd
abedc

输出样例：

1
3

思路分析

状态表示：表示的前个字符和的前个字符的最长子序列长度。

状态计算：

如果，那么显然不会超过和的最大值；又因为也不会比他们任何一个小，因此

如果，那么显然

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

char a[N], b[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;
    for (int i = 1; i <= n ;i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) 
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m];
    return 0;
}

最短编辑距离

题干

给定两个字符串 和 ，现在要将 经过若干操作变为 ，可进行的操作有：

  1. 删除–将字符串 中的某个字符删除。
  2. 插入–在字符串 的某个位置插入某个字符。
  3. 替换–将字符串 中的某个字符替换为另一个字符。

现在请你求出，将 变为 至少需要进行多少次操作。

输入格式

第一行包含整数 ，表示字符串 的长度。

第二行包含一个长度为 的字符串 。

第三行包含整数 ，表示字符串 的长度。

第四行包含一个长度为 的字符串 。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

输入样例：

1
2
3
4
10
AGTCTGACGC
11
AGTAAGTAGGC

输出样例：

1
4

思路分析

状态表示：表示的前个字符变为的前个字符的最少操作次数。

状态计算：显然、​地位等价，讨论其中之一即可。

若

如果删除后可以变为，那么要先做到与匹配，即

如果插入后可以变为，那么插入的就是，要先做到与匹配，即

若

如果替换​为​后可以变为​，那么要先做到​与​​​匹配；

如果，那么此时不需要替换，即

如果，那么此时需要替换，即

由于中类型默认为1，类型默认为0，因此可以统一写成

最后的即为这三种情况取最小值。

注意：此题求最小值，记得初始化，否则答案会输出0；初始化时，把与都初始化为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

char a[N], b[N];
int f[N][N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> a + 1 >> m >> b + 1;
    for (int i = 0; i <= n; i++)
        f[i][0] = i;
    for (int i = 0; i <= m; i++)
        f[0][i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    cout << f[n][m];
}

编辑距离

题干

给定 个长度不超过 的字符串以及 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含一个字符串，表示给定的字符串。

再接下来 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 。

输出格式

输出共 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

输入样例：

1
2
3
4
5
6
3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
2
1
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
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 1010;

char str[M][M];
int f[N][N];

int edit_dist(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);
    // 由于我们输入字符串的时候都没有用[0]，因此求长度也要从a[i],b[i]开始求
    for (int i = 0; i <= la; i++)   f[i][0] = i;
    for (int i = 0; i <= lb; i++)   f[0][i] = i;
    for (int i = 1; i <= la; i++)   
        for (int j = 1; j <= lb; j++)
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    return f[la][lb];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> str[i] + 1;
    // str[i] 成为1-base，也就是从str[i][1]开始存
    while (m--)
    {
        char que[N];
        int dist;
        cin >> que + 1 >> dist;
        int res = 0;
        for (int i = 1; i <= n; i++)
            if (edit_dist(str[i], que) <= dist) res++;
        cout << res << '\n';
    }
}

区间DP

石子合并

题干

设有 堆石子排成一排，其编号为 。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 表示石子的堆数 。

第二行 个数，表示每堆石子的质量(均不超过 1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

输入样例：

1
2
4
1 3 5 2

输出样例：

1
22

思路分析

状态表示：表示合并从到的所有石子的体力最小值，则即为所求。

状态计算：类似于归并思想，考虑的上一步，它一定是由两堆石子合并而来，分别为和，其中。因此只需要计算对于所有，和的最小值即可。由于将这两堆合并还需要体力，而这些体力为一个与无关的常数，因此可以求完最值再加上去；由于要重复利用这段求和，可以使用前缀和数组先求出来避免重复计算。

如何写循环？我们要保证一点：当我们执行下一批循环的时候，上一批循环的每个元素都要是我们已知的；而对于这种方法，下一批循环比上一批循环一定保证的特点是区间长度更长，因此我们可以根据区间长度为循环依据。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 310;

int a[N], s[N];
int f[N][N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];

    for (int len = 2; len <= n; len++)
        for (int l = 1, r = l + len - 1; r <= n; l++, r++)
        {
            f[l][r] = 0x3f3f3f3f;
            for (int k = l ; k <= r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    cout << f[1][n];
    return 0;
}

计数类DP

整数划分

题干

一个正整数 可以表示成若干个正整数之和，形如：，其中 。

我们将这样的一种表示称为正整数 的一种划分。

现在给定一个正整数 ，请你求出 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 取模。

数据范围

输入样例:

1
5

输出样例：

1
7

思路分析

状态表示：表示总划分数量，而肯定得有一个值代表被划分的数，这里我们选择；而对于，我们思考：有哪些可取的表示？一种是类似背包问题，表示可用的数字为从，另一种是代表划分后数字的数量，表示数量有个。

状态计算：对于第一种，仍然考虑和背包问题类似的划分，也就是根据的划分中的数量决定分组；此时有点类似完全背包问题，有
其中即
记得数组的初始化：如果，那么唯一的方式就是不选数字，此时有一种选法；如果，此时选法就是选个，此时有一种选法；如果，此时有0种选法；显然当，以此类推有，因此只需要初始化​的情况；又因为时初始化为0，而全局数组默认为0，因此只需要初始化情况。

注意：与背包问题类似，​​不一定存在，记得特判。

法1：完全背包解法

版本1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;

int f[N][N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
        f[i][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= i)
                f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }
    cout << f[n][n];
}

由于这题本质上是个完全背包问题，因此可以用一维数组优化，而遍历时为顺序遍历。

版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;

int f[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
                f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n];
}

对于第二种，表示划分成个数字的方法数总和，那么如果我们想用进行递推，我们要确保的问题是：这个数字中有没有。

如果有数字，那么我们把这个去掉，此时相当于划分成个数，也就是；如果没有数字，那么我们就把每一个元素都减去，此时仍然有个数字，但他们的和变成了，即。得到递推公式

初始化：显然当时，仅有，其余均为0。

注意：与法一不同点在于最后计算答案的时候要求和。

法二

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;

int f[N][N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j - 1];
            if (j >= i)
                f[i][j] = (f[i][j] + f[i][j - i]) % mod;
        }
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + f[i][n]) % mod;
    cout << res;
}

状态压缩DP

蒙德里安的梦想

题干

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

例如当 ， 时，共有 种方案。当 ， 时，共有 种方案。

如下图所示：

image-20251203151623929

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 和 。

当输入用例 ， 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

输入样例：

1
2
3
4
5
6
7
8
9
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
2
3
4
5
6
7
8
1
0
1
2
3
5
144
51205

思路分析

此题状态表示为状态压缩 dp，即把一个状态对应成一个二进制数来表示，形成状态和数字的一一对应。

同时考虑横块与竖块太过麻烦，不妨只考虑横块：如果横块的放置方法都确定，那么竖块的放置方法也一定确定：一列一列放下去，如果遇到连续的奇数空格则这个方法不合法，反之如果都是连续的偶数空格就合法；因此只需要枚举横块的放置方式，再判断横块的放置方式下是否合法即可。

状态表示：表示在第列不放置方块的时候，第列的方块伸到第列的状态压缩数为，此时总方案数为​。

例如，第一列放置方块的状态为F、T、T、F、F，对应的状态就是​

状态计算：定义可知，第列不放方块，第列放方块状态为，这两列均确定；此时考虑第列，不妨设列放方块的模式为，即有和。那么所谓“合法”，就是满足以下两个条件：

  1. Misplaced &j &k=0 这里是按位与，也就是对于和的压缩，不能有任何一位均为1；这很好理解，表示列伸到列的方块状态，表示列自己放置的方块状态，如果这两个均为1，那么就重叠了。
  2. 的二进制表示不存在连续的奇数个0。与上述理解相同，这两个都表示列的方块情况，如果出现连续的奇数0说明列不合法。

对于合法的条件，要怎么计算总数呢？直接相加即可，即
其中合法
为了方便后续使用，我们可以将合法要求2（因为合法要求1只需要一条式子就可以表达）先计算出来，也就是对于所有的数，计算出他们的二进制合不合法。计算方法是：对于每个数，进行取每一位的循环；如果为0，就用cnt记录；如果为1，就看看此时cnt是奇数还是偶数，是奇数直接不合法，是偶数继续循环；如果全为0，那么在最后单独补一次是否合法的判断。

注意：在计算是否合法时，一定要在n确定的情况下进行，而不能在外部预处理。比如时的表示为，此时不合法，因为有3个连续的0；但时的表示为​，此时合法。

初始化：显然第0列不会出现上一列伸过来的情况，因此第0列只有全空一种情况，即；最后答案输出，我需要保证第列（即最后一列，因为使用）没有东西伸到第列，所以输出即可。

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
91. 最短Hamilton路径#include <bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << 12; 

long long f[N][M];
bool st[M];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m;
    while (cin >> n >> m, n || m)
    {
        int states = 1 << n;
        for (int i = 0; i < states; i++)
        {
            st[i] = true;
            int cnt = 0;
            for (int j = 0; j < n; j++)
            {
                if (i >> j & 1)
                {
                    if (cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                }
                else cnt++;
            }
            if (cnt & 1)
                st[i] = false;
        }
        memset(f, 0 ,sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m ;i++)
            for (int j = 0; j < states; j++)
                for (int k = 0; k < states; k++)
                    if ((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << '\n';
    }
}

最短Hamilton路径

题干

给定一张 个点的带权无向图，点从 标号，求起点 到终点 的最短 Hamilton 路径。

Hamilton 路径的定义是从 到 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 。

接下来 行每行 个整数，其中第 行第 个整数表示点 到 的距离（记为 ）。

对于任意的 ，数据保证 ， 并且 。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围


输入样例：

1
2
3
4
5
6
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

1
18

思路分析

简单的思路是：对于每一个点，假设走了步走到点，那么只要对走了步，并且下一步是从其他点走到的路线进行DP即可。

问题是：首先我们不知道这步是否经历一个点，因此不能对所有的点都遍历；其次我们无法表示出“走了步并且下一步是走到”的状态。为了解决这个问题，我们需要知道我们之前经历了哪些点，再加上本题数据比较小，因此选择状态压缩。

状态表示：显然必须有一个值表示经过了哪些点，记为，Misplaced &i>>k\ &\ 1表示经过了点，例如经历就可以表示为；除此之外，我们还需要我们目前到达了哪个点；并且我们维护的状态是路径的最小值，因此有
表示经过的点状态为，终点为的路径长度最小值
状态计算：根据之前的分析，在进行状态计算前，我们首先要判断点是否走过，即判断Misplaced &i>>k\ &\ 1；其次，如何表示上一个点？首先上一个点的终点比较简单，是我们遍历的；而上一个点的状态，是当前点的状态再减去这个点的状态。因此有递推关系式
Misplaced & f(i,j) = min(f(i-(1<<j),k)+a[j][k])，其中k满足i>>k \ & \ 1=1
初始化：首先由于我们用到了最小值函数，因此应该将数组初始化为无穷大；接着把这个点本身初始化为0，即；其次，我们应该将一步可以走到的地方直接写出来，如​，显然此时前者为无穷大，而后者为到的距离，也就是循环过程中会自动把这个赋值好。

循环代码注意事项：首先我们是对所有、遍历，有可能会出现根本不在标识的状态内的情况，因此要先判断Misplaced &i>>j \ & \ 1=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
#include <bits/stdc++.h>
using namespace std;
const int N = 21, M = 1 << N;

int a[N][N], f[M][N];
int n;
// f[i][j] 表示走过的点为i(状态压缩), 终点为j的最短距离
// 判断是否走过点k: i >> k & 1

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

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

    // 计算f[i][j]
    for (int i = 1; i < (1 << n); i++)
        for (int j = 1; j < n; j++)
            if (i >> j & 1)
                for (int k = 0; k < n; k++)
                    if ((i >> k & 1) && j != k)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[j][k]);
    cout << f[(1 << n) - 1][n - 1];
    return 0;
}

树形DP

没有上司的舞会

题干

Ural 大学有 名职员，编号为 。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 。

接下来 行，第 行表示 号职员的快乐指数 。

接下来 行，每行输入一对整数 ，表示 是 的直接上司。（注意一下，后一个数是前一个数的父节点，不要搞反）。

输出格式

输出最大的快乐指数。

数据范围

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

1
5

思路分析

所有职员的上下属关系会形成一个树，因此可以使用树形DP来解决。由于选择了一个职员后就不能再选择其上司，因此可以分为两种情况：选择该职员或者不选。

状态表示：表示以为根的子树中，选择的情况下的最大快乐指数；表示以为根的子树中，不选择的情况下的最大快乐指数。

状态计算：对于每个节点，如果选择了，那么它的子节点就不能选择，因此有

如果不选择，那么它的子节点可以选择也可以不选，因此有

注意事项：由于本题是树，因此要用存储图的方式（邻接表）来存储数据，同时由于要用到子节点的结果，要进行DFS；由于并没有告诉我们树根是谁，因此我们要自己找出树根，方法也很简单：找到没有父结点的结点即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;

int h[N], e[N], ne[N], happy[N];
bool has_father[N];
int f[N][N];
int idx = 1, n;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

void dfs(int u)
{
    f[1][u] = happy[u];
    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[1][u] += f[0][j];
        f[0][u] += max(f[0][j], f[1][j]);
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> happy[i];
    for (int i = 1; i < n; i++)
    {
        int l, k;
        cin >> l >> k;
        add(k, l);
        has_father[l] = true;
    }
    
    int root = 1;
    while (has_father[root]) root++;
    dfs(root);
    cout << max(f[1][root], f[0][root]);
}

记忆化搜索

滑雪

题干

给定一个 行 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 行第 列的点表示滑雪场的第 行第 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

1
2
3
4
5
 1  2  3  4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

在给定矩阵中，一条可行的滑行轨迹为 。

在给定矩阵中，最长的滑行轨迹为 ，沿途共经过 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围


矩阵中整数

输入样例：

1
2
3
4
5
6
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例：

1
25

思路分析

状态表示：表示从出发的最长滑雪路径长度，由于每次只能向高度更低的区域滑动，而高度更低的区域可能路径长度未知，因此可以使用DFS+记忆化搜索来解决。

状态计算：从出发，可以向上下左右四个方向滑动，假设滑动到，那么有
其中满足在矩阵范围内，且高度小于。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 310;

int mp[N][N];
int f[N][N];
int n, m;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

int dp(int x, int y)
{
    if (f[x][y]) return f[x][y];
    f[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && mp[x][y] > mp[xx][yy])
        {
            dp(xx, yy);
            f[x][y] = max(f[x][y], f[xx][yy] + 1);
        }
    }
    return f[x][y];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
            
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp(i, j);
            
    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = max(res, f[i][j]);
    cout << res;
}