前言

动态规划，DP(Dynamic Programming)，运筹学的一个分支，同时也是求解决策过程最优化问题的过程。它和贪心一样，不是具体的某一种算法，而是一种思想。

DP的学习和使用，非常地具有挑战性，会使用DP，经常可以写出令人拍案叫绝的代码。所以它也是算法竞赛，数学建模等中的一个热点问题

DP优化是对方程进行等价变换

背包问题

背包问题解决的是 组合问题的最优解 这一类问题

状态表示与计算

f(i,j)f(i,j)存的是集合中所有选法的属性，是一个数

集合划分

0-1背包

每个物品只能选一次，即放入/不放入背包，使利益最大化

01背包问题（状态转移方程讲解）深蓝

状态转移方程：

f[i,j]=max(f[i−1,j],f[i−1,j−v]+w)f[i,j] = max(f[i-1,j],f[i-1,j-v]+w)

二维

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 <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 当前背包容量小于物品重量
            if (j < v[i])   f[i][j] = f[i-1][j]; // 表示不选
            else f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]); // 表示选上
        }
    }
    cout << f[n][m] << endl;
    
    return 0;
}

一维

关于内层循环要为何要逆序遍历？

如果顺序遍历，那么数组中来自上一轮的状态，会因顺序原因被污染。导致出现需要上一轮的状态时，却已经被覆盖了的情况。

换言之，如果j是顺序递增的话,则相当于f[i][j]变得是由f[i][j-v[i]]推出来的，

而不是由原来的f[i-1][j-v[i]]推的。与我们的状态转移方程不符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) 
        for (int j = m; j >= v[i]; j--) 
            f[j] = max(f[j], f[j-v[i]] + w[i]);
    
    cout << f[m] << endl;
    
    return 0;
}

AcWing.0-1背包

《信息学奥赛一本通》糖果(01背包)

完全背包

物品无限量，同一个物品可以重复放入背包中

第八届蓝桥杯省赛C++A/B组-包子凑数(完全背包+数论)

O(n^3)，朴素做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m; // 物品数量，背包容量
int v[N], w[N]; // 体积，价值
int f[N][N];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ ) // 物品
        for (int j = 0; j <= m; j++) // 重量
            for (int k = 0; k * v[i] <= j; k++) // 物品个数
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
                
    cout << f[n][m] << endl;
    
    return 0;
}

O(n^2)

对k进行优化，三维降二维，状态转移方程优化推导如下：

f[i,j]=max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2v]+2w,...)f[i,j] = max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...)

因为i-1个物品的最大值已经在上一轮循环确定了下来，所以我们只需讨论第i个物品应该选多少个

将j替换为j-v

f[i,j−v]=max(f[i−1,j−v],f[i−1,j−2v]+w,f[i−1,j−3v]+2w,...)f[i,j-v] = max(f[i-1,j-v],f[i-1,j-2v]+w,f[i-1,j-3v]+2w,...)

f[i,j−v]+w=max(f[i−1,j−v]+w,f[i−1,j−2v]+2w,f[i−1,j−3v]+3w,...)f[i,j-v]+w = max(f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,...)

将上述式子代入原方程，进行等价替换，得到状态转移方程：

f[i,j]=max(f[i−1,j],f[i,j−v]+w)f[i,j]=max(f[i-1,j],f[i,j-v]+w)

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 <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

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

降维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    
    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 <= m; j++) // 从小到大循环
            f[j] = max(f[j], f[j-v[i]] + w[i]);
                
    cout << f[m] << endl;
    
    return 0;
}

同时处理输入和状态转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int f[N];

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

多重背包

每个物品的数量不同

朴素作法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main() {
    cin >> n >> m;
    
    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 <= m; j++)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i-1][j-v[i]*k] + w[i]*k);
    
    cout << f[n][m] << endl;
    
    return 0;
}

二进制优化

将一个物品的个数，表示成一段从1开始的二进制数

例如，200：1、2、4、8、16、32、64、73

为什么不选128呢？因为如果加128，可以表示的数就达到了255，超出了200。到64时，表示的数范围为127，补上一个73，就能够表示从1-200之间的任何一个数

  • 同时留意使用二进制优化时，需要开辟的数组空间为物品种数xlog2(某种物品的数量，向上取整)。因为我们在把物品数量拆成二进制表示时，要考虑到要用多少个数，才能表示出物品数量，得出上述结果
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 <iostream>
#include <algorithm>
using namespace std;
// 当有1000种物品，每种物品的数量为2000，得25000
const int N = 25000; // 留意开辟空间
int f[N];
int v[N], w[N];
int n, m;

int main() {
    cin >> n >> m;
    
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int a, b, s;
        cin >> a >> b >> s;
        
        // 二进制优化核心代码
        int k = 1;
        while (k <= s) {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0) {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    
    // 0-1背包
    for (int i = 1; i <= n; i++) 
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j-v[i]] + w[i]);
            
    cout << f[m] << endl;
    
    return 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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int f[N];
int v[N][N], w[N][N], s[N];

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

线性DP

数字三角形

DP里的Hello World!

数字三角形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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N], f[N][N];

int main() {
    cin >> n;
    
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= i; j++) 
            scanf("%d", &a[i][j]);
    
    for (int i = 0; i <= n; i++) 
        for (int j = 0; j <= i + 1; j++) // 每行需要多初始化一个，考虑到两边
            f[i][j] = -INF;
    
    f[1][1] = a[1][1];
    
    for (int i = 2; i <= n; i++) // 若从1开始，结果为负无穷，由前状态转移而来
        for (int j = 1; j <= i; j++) // 从2开始才有前状态
            f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j]);
        
    int res = -INF;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
        
    cout << res << endl;
    
    return 0;
}

AcWing.数字三角形

最长上升子序列

到这里为止，学习动态规划的感想是：根据题目，找到其中的一个状态，分析它是由前一个状态怎么转换得来。

比方说到下图中的6这个位置上，那么要求以6结尾的最长递增子序列要通过遍历它的前六个数，判断与它们的大小关系，再加1，取最大值。而前6个数的最长又是怎么求出来的？就是根据前5个数，以此类推

image-20220220115331498 最长上升子序列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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], f[N], pre[N];
int n;

void PrintPath(int v) {
    if (pre[v] == 0) {
        printf("%d", a[v]);
        return;
    }
    PrintPath(pre[v]);
    printf(" %d", a[v]);
}

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) {
        f[i] = 1; // 初始化，只有1个数以第i个数结尾
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                if (f[i] < f[j] + 1) {
                    f[i] = f[j] + 1;
                    pre[i] = j; // 记录前一个点的下标，用于还原路径
                }
            }
        }
    }

    int res = -1e9, t;
    for (int i = 1; i <= n; i ++ ) {
        if (f[i] > res) {
            res = f[i];
            t = i; // 记录最长路径的最后一个下标
        }
    }
    cout << res << endl;
    PrintPath(t);

    return 0;
}

AcWing.最长上升子序列

最长公共子序列

  • 状态表示f[i,j]f[i,j]：s1的前i个字符和s2的前j个字符的最长公共子序列
  • 状态计算：s1[i]=s2[j]s_1[i] = s_2[j] 和 s1[i]!=s2[j]s_1[i] != s_2[j]

当两个字符相等时，容易理解，由f[i−1][j−1]+1f[i-1][j-1] + 1转移而来

而当两个字符不等时，两个字符中一定有一个可以抛弃f[i−1][j],f[i][j−1]f[i-1][j], f[i][j-1]另外一个可能存在于最长序列，也有可能不存在，取最大值避免了复杂的讨论情况

2022-3-27，今天做到了一个密码脱落问题，对这种类型的题状态不完全相等，而是存在覆盖有了更深的理解。

当两个字符串中待匹配的字符不相等时，我们可以舍弃其中任一一个，也可以两个都舍弃。但是状态虽可以这么划分，但真正实现时，其实没有一种写法可以完全等同于这种思路，只能做到包含关系。比如我们抛弃的是前一个，而留下后一字符串（这是我们划分状态阶段所希望的）；然后f[i−1][j]f[i-1][j]实际的含义是，前一个确实被抛弃，但j可能被留下，也有可能也被抛弃，而无法做到完全和状态等同，但这种状态包含了前一种。这也是为什么两种字符都抛弃的f[i−1][j−1]f[i-1][j-1]状态可以省略，不用写出，因为它包含在了f[i−1][j],f[i][j−1]f[i-1][j], f[i][j-1]中。

满足了状态计算时重复了，但由于求的是Max，所以结果不受到影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char s1[N], s2[N];
int f[N][N];

int main() {
    cin >> n >> m >> s1 + 1 >> s2 + 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 (s1[i] == s2[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }
    cout << f[n][m] << endl;
    return 0;
}

AcWing.最长公共子序列

第七届蓝桥杯省赛C++A组——密码脱落(类似题)

最短编辑距离

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

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

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

状态表示f[i][j]f[i][j]：A的前i的字符与B的前j个字符成功匹配需要操作的最少次数

状态计算：

  • f[i−1][j]+1f[i-1][j]+1：删除操作，A的前i-1个字符已经与b的前j个字符匹配上，选择删除A的第i个字符
  • f[i][j−1]+1f[i][j-1]+1：插入操作，A的前i个字符已经与b的前j-1个字符匹配上，选择在A中插入一个与B[j]相同的字符完成匹配
  • f[i−1][j−1]+1f[i-1][j-1]+1：修改操作，当AB待比较的两个字符不相等时，改变A中的第i个字符，使其与B相等。而在这之前A的i-1个字符与B的j-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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
char a[N], b[N];
int n, m;
int f[N][N];

int main() {
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);
    
    for (int i = 0; i <= m; i++) f[0][i] = i;
    for (int i = 0; i <= n; i++) f[i][0] = i;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i-1][j-1]);
            else f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
        }
    }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

区间DP

这里选取了区间DP非常有代表性的三道题，三题之间层层递进，有助于理解好区间DP

区间DP常用代码模板，点击链接或如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            f[i][j] = 初始值
            continue;
        }

        for (int k = i; k < j; k++) {        // 枚举分割点，构造状态转移方程
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + w[i][j]);
        }
    }
}

石子合并

《算法竞赛进阶指南》石子合并

  • 状态表示f[i,j]f[i,j]：从第i堆石子到第j堆石子合并所需的代价
  • 状态计算：将区间划分成[i,k][i,k]和[k+1,j][k+1,j]，k=i,i+1,...,j−1k = i, i+1, ..., j-1

通过枚举区间长度，找出代价的最小值

状态转移：f[l][k]+f[k+1][r]+s[r]−s[l−1]f[l][k] + f[k+1][r] + s[r] - s[l-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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n;
int f[N][N];
int s[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
    // 前缀和，确定任一区间的权重
    for (int i = 1; i <= n; i ++ ) s[i] += s[i-1];
    
    // len=1的时候无须合并，所以从2开始
    for (int len = 2; len <= n; len++)			// 区间长度
        for (int i = 1; i + len - 1 <= n; i++) {// 枚举起点
            int l = i, r = i + len -1;
            f[l][r] = 1e8;
            // 在区间范围内进行划分
            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] << endl;
    
    return 0;
}

密码脱落

第七届蓝桥杯省赛C++A/C组-密码脱落

给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在这样

原先至少脱落多少的种子=现在再脱落多少的种子=总长度-最大回文子序列

最大回文子序列状态分析

dbeb2ca84e7ee6b21319802cbd0170d.png

图片原地址

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 <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1010;
char str[N];
int f[N][N];

int main() {
    scanf("%s", str);
    int n = strlen(str);
    for (int len = 1; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (l == r) f[l][r] = 1;
            else {
                if (str[l] == str[r]) f[l][r] = f[l+1][r-1] + 2;
                if (f[l+1][r] > f[l][r]) f[l][r] = f[l+1][r];
                if (f[l][r-1] > f[l][r]) f[l][r] = f[l][r-1];
            }
        }
    }
    cout << n - f[0][n-1] << endl;
    
    return 0;
}

括号配对

密码脱落+石子合并结合版

《信息学奥赛一本通》- 括号配对

以下是 GBE 的定义：

  • 空表达式是 GBE
  • 如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
  • 如果 A 与 B 都是 GBE，那么 AB 是 GBE（区别于普通回文串的地方）

下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。

image-20220329144412463

状态计算分析

左半边

  • i、j都被用上，即i、j匹配成功，是左右括号关系，那么要求添加多少字符应该进一步到f[i+1][j-1]当中求解
  • 如果i,j有一个不在最终GBE中，即需要一个字符与它匹配，会等于f[i+1][j]+1。这一步会有一个状态包含关系，详情请见石子合并

右半边

  • 左边第一个完整括号的长度
  • 假设此时[i,k]匹配成功了，那么最小值等于f[i][k]+f[k+1][j]。这里依旧有个包含关系，因为深入到[i,k]当中，可能仍有不完整的符号
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 N = 110, INF = 1e9;
int f[N][N];

bool is_match(char l, char r) {
    if (l == '(' && r == ')') return true;
    if (l == '[' && r == ']') return true;
    return false;
}

int main() {
    string str;
    cin >> str;
    int n = str.size();
    if (n == 1) { // 特判
        cout << 1 << endl;
        return 0;
    }
    
    for (int len = 1; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            f[l][r] = INF;
            // 左半边
            if (is_match(str[l], str[r])) f[l][r] = f[l+1][r-1];
            if (r >= 1)
                f[l][r] = min(f[l][r], min(f[l+1][r], f[l][r-1]) + 1);
            // 右半边
            for (int k = l; k < r; k++) // 枚举第一个完整括号的区间
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r]); 
        }
    }
    cout << f[0][n-1] << endl;
    
    return 0;
}

计数类DP

状态表示中属性为count的DP问题

鸣人的影分身-计数DP

整数划分

一个正整数n可以表示 成若干个正整数之和，形如：n=n1+n2+...+nkn = n_1 + n_2 + ... + n_k，其中n1≥n2≥...≥nk,k≥1n_1 \ge n_2 \ge ... \ge n_k, k \ge 1。

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

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

输入格式

共一行，包含一个整数n。

输出格式

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

由于答案可能 很大，输出结果请对109+710^9+7取模。

数据范围

1≤n≤10001 \le n \le 1000

转化为完全背包问题

  • 状态表示f[i,j]f[i,j]：从1-i当中选，使体积恰好是j的数量
  • 状态计算：针对第i个数时，有不选、选i、选2i、……、选si这些情况，容易将其转化为完全背包问题

选几个i，就要在之前的状态中提前预留出位置，因此减去

f[i,j]=f[i−1,j]+f[i−1,j−i]+f[i−1,j−2i]+...+f[i−1,j−si]f[i,j] = f[i-1,j]+f[i-1,j-i]+f[i-1,j-2i]+...+f[i-1,j-si]

将j等价替换为j-i

​ f[i,j−i]=f[i−1,j−i]+f[i−1,j−2i]+f[i−1,j−3i]+...+f[i−1,j−si]f[i,j-i] = f[i-1,j-i]+f[i-1,j-2i]+f[i-1,j-3i]+...+f[i-1,j-si]

代入原式，得

f[i,j]=f[i−1,j]+f[i,j−i]f[i,j]=f[i-1,j]+f[i,j-i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];

int main() {
    cin >> n;
    
    f[0] = 1; // 一个数都不选，总和为0时的方案
    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] << endl;
    
    return 0;
}

计数类DP

  • 状态表示f[i,j]f[i,j]：所有数的总和为i，并且表示成j个数的和的个数
  • 状态计算：将集合划分成两种情况：j个数中最小值为1和最小值大于1
    • 最小值为1：f[i−1,j−1]f[i-1,j-1]
    • 最小值大于1：f[i−j,j]f[i-j,j]（每个值都减去1，一共减j，方案数不变）

状态转移方程为

f[i,j]=f[i−1,j−1]+f[i−j,j]f[i,j]=f[i-1,j-1]+f[i-j,j]

最后的结果需要对式求和f[n][i],i=1,2,...,nf[n][i],i=1, 2,...,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
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int main() {
    cin >> n;
    
    f[0][0] = 1;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;
    
    cout << res << endl;
    
    return 0;
}

数位统计DP

计数问题

给定两个整数 aa 和 bb，求 aa 和 bb 之间的所有数字中 0∼90∼9 的出现次数。

  • 解法一：暴力枚举

  • 解法二：枚举每一位上x出现的次数

举例如下

abcdefgabcdefg

x在第4位(d)上出现的次数

  1. 000∼abc−1000∼abc-1，出现abc∗1000abc*1000次，1000为10^efg的长度

    判断的数在最高位时，不用考虑情况1

    这里需要讨论一种特殊情况，若判断的x是0出现的次数，则要从001开始，意味着(abc−1)∗1000(abc-1)*1000

  2. abcabc

    1. d<xd<x，出现0次
    2. d=xd=x，出现efg+1efg+1次(000)
    3. d>xd>x，出现1000次(efg:000-999)

另外一种特殊情况是，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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a, b;

// 求10^x
int power10(int x) {
    int res = 1;
    while (x--) {
        res *= 10;
    }
    
    return res;
}

// 将num中l到r表示的数提取成一个数
int get(vector<int> num, int l, int r){
    int res = 0;
    
    for (int i = l; i >= r; i--) {
        res = res * 10 + num[i];
    }
    
    return res;
}

// 数位DP
int count(int n, int x) {
    // 1到0中不含有任何数
    if (!n) return 0;
    
    vector<int> num;
    
    // 将n倒序存放
    while (n) {
        num.push_back(n % 10);
        n /= 10;
    }
    
    // 获取n的位数，用于遍历
    n = num.size();
    
    int res = 0;
    // 遍历x在n的每一位上出现的次数，并作和
    // 若x为0，则x必不出现在n的最高位，直接从第二位开始计算
    for (int i = n - 1 - !x; i >= 0; i--) { // 枚举在第i位上，x出现的次数
        // 情况一
        if (i < n - 1) {
            res += get(num, n-1, i+1) * power10(i);
            if (!x) res -= power10(i);
        }
        // 情况二
        if (num[i] == x) res += get(num, i-1, 0) + 1;
        else if (num[i] > x) res += power10(i);
        
    }
    
    return res;
}
// 暴力解法
int force_count(int n, int x) {
    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j; j /= 10)
            if (j % 10 == x) res++;
    
    return res;
}
int main() {
    
    while (cin >> a >> b, a || b) {
        if (a > b) swap(a, b);
        for(int i = 0; i < 10; i++) {
            // 以前缀和的方式，求ab区间i出现的次数
            cout << count(b, i) - count(a-1, i) << ' ';
        }
        cout << endl;
    }
    
    return 0;
}

AcWing 338. 计数问题

状态压缩DP

所谓的状态压缩DP，就是用二进制数保存状态。

通过几道题，得出状态压缩问题有点类似蒙特卡罗。状态压缩DP通过枚举二进制来表示每一状态，和蒙特卡罗中枚举随机数来得到最后的答案非常的相似。

状态压缩位数N≤20N \le 20，约等于数据量10610^6

蒙德里安的猜想

  • 状态表示f[i,j]f[i,j]：f[i][j]表示已经将前 i -1 列摆好，且从第i−1列，伸出到第i列的状态是j的所有方案数。且j是一个由二进制表示出来的数，如10010：第1列和第4列有砖
  • 状态计算：f[i,j]+=f[i−1,k]f[i,j]+=f[i-1,k]

状态转移需要满足两个条件：

  1. 不与前一个状态冲突(j&k)==0
  2. 此状态中0的个数(j|k)为偶
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 <cstring>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;
bool st[M];
int n, m;
long long f[N][M];

int main() {
    while (cin >> n >> m, n || m) {
        // 枚举所有奇数个0的状态，并将其设置为false
        for (int i = 0; i < 1 << n; i++) {
            st[i] = true;
            int cnt = 0;
            
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                } 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 < 1 << n; j++)
                for (int k = 0; k < 1 << n; k++)
                    // 若不与前一个状态冲突且此状态中0的个数为偶 
                    if ((j & k) == 0 && st[j|k]) f[i][j] += f[i-1][k];
            
        cout << f[m][0] << endl;
    }
    
    return 0;
}

291.蒙德里安的梦想

最短Hamilton路径

  • 状态表示f[i,j]f[i,j]：走过的点用二进制记录在i中，从0到达j的最短路径
  • 状态计算：f[i,j]=f[i−j,k]+w[k.j]f[i,j]=f[i-{j}, k] + w[k.j]

二进制数100101意思是经过了第1、3、6点（倒着看）

​ 0->…->k->j

从k走到j点需要满足条件：k可以到达j。

不过在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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];

int main() {
    cin >> n;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];
    
    memset(f, 0x3f, sizeof f);
    
    // 初始化，当在第一个点时，路径为0
    f[1][0] = 0;
    
    for (int i = 0; i < 1 << n; i++) // 枚举可能的所有到达情况
        for (int j = 0; j < n; j++) // 枚举，当前到达了j点
            if (i >> j & 1) // 表示从0可以到达j点
                for (int k = 0; k < n; k++) // 枚举点k(j的前一个点)
                    if ((i - (1 << j)) >> k & 1) // 先减掉目的点j后，需要先能到达k点
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
            
    cout << f[(1 << n)-1][n-1] << endl;
    
    return 0;
}

91.最短Hamilton路径

树形DP

左孩子右兄弟(树形DP)

没有上司的舞会

一道非常经典的树形DP问题

  • 状态表示f[i][0],f[i][1]f[i][0],f[i][1]：0表示当前i结点不选，1表示选
  • 状态计算：f[i][0]+=max(f[j][0],f[j][1])f[i][0] += max(f[j][0], f[j][1]) f[i][1]+=f[j][0]f[i][1] += f[j][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
44
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int h[N], e[N], ne[N], idx;
int happy[N];
bool st[N];
int f[N][2]; // 树形DP

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

void dfs(int u) {
    f[u][1] = happy[u];
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        // 上司不去舞会
        f[u][0] += max(f[j][0], f[j][1]);
        // 上司去舞会
        f[u][1] += f[j][0];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> happy[i];
    memset(h, -1, sizeof h);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        st[a] = true;
        add(b, a);
    }
    int root = 1;
    while(st[root]) root++;
    dfs(root);
    cout << max(f[root][0], f[root][1]) << endl;
    
    return 0;
}

285.没有上司的舞会

翻转树边(换根DP)

Keywords: 数组模拟邻接表，树形DP，传递边的编号

第一届ACC决赛-翻转树边(原题链接)

给定一个 nn 个节点的树。

节点编号为 1∼n1∼n。

树中的 n−1n−1 条边均为单向边。

现在，我们需要选取一个节点作为中心点，并希望从中心点出发可以到达其他所有节点。

但是，由于树中的边均为单向边，所以在选定中心点后，可能无法从中心点出发到达其他所有节点。

为此，我们需要翻转一些边的方向，从而使得所选中心点可以到达其他所有节点。

我们希望选定中心点后，所需翻转方向的边的数量尽可能少。

  • 请你确定哪些点可以选定为中心点，并输出所需的最少翻转边数量。

这里对y总的思路再进行分析。

image-20220328111156536

这道题如果求的是根结点直接作为中心点，到其它节点所需要翻转边的数量，那么就非常简单，直接dfs一遍即可，令正边权值为0，反向边权值为1，如上图所示

image-20220328110855591

但是这道题提高了一点难度，要求我们找到这样的一个中心点，它到所有其它点所要翻转的边最少，因此要采取换根遍历 。

  • 使用down[]记录当前节点往下走，所要翻转的边数。可以递归先求出每个子节点，最后汇总到根节点

  • 使用up[]记录往上走要翻转的边的数量，先计算根节点，再计算子节点如上图我们分析得up[u]=up[fa]+down[fa]−down[u]−w+w′up[u]=up[fa]+down[fa]-down[u]-w+w'

实现上，由于使用了数组模拟邻接表，我们在创建邻接表时，会自动将编号为01，23，45，67……划为一组，表示反向边，通过异或运算实现（2^1=3,3^1=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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10, M = 2 * N;
int h[N], e[M], w[M], ne[M], idx;
int down[N], up[N];
int n;
// 数组模拟邻接表
void add(int a,int b, int c) { // a->b
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 当前节点向下搜
void dfs_down(int u, int from) {
    // from为边的编号，容易求出反向边
    for (int i = h[u]; ~i; i = ne[i]) {
        if (i == (from ^ 1)) continue; // 边是双向的，避免往回搜，出现死循环
        int j = e[i];
        dfs_down(j, i);
        down[u] += down[j] + w[i];
    }
}
// 当前节点往上搜
void dfs_up(int u, int from) { 
    if (from != -1) {
        int fa = e[from ^ 1]; // 反向边的终点
        up[u] = up[fa] + down[fa] - down[u] - w[from] + w[from^1];
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        if (i == (from ^ 1)) continue;
        int j = e[i];
        dfs_up(j, i);
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b, 0);
        add(b, a, 1);
    }
    
    dfs_down(1, -1);
    dfs_up(1, -1);
    
    int res = N;
    for (int i = 1; i <= n; i++) 
        res = min(res, down[i] + up[i]);
    
    printf("%d\n", res);
    for (int i = 1; i <= n; i++)
        if (down[i] + up[i] == res) printf("%d ", i);
    
    return 0;
}

生命之树

传递点的编号，数组模拟邻接表

第六届蓝桥杯省赛C++B组-生命之树

寻找树中的某一连通块，使其权值和最大

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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 2*N;
int n;
int h[N], e[M], ne[M], idx;
int w[N];
LL f[N]; // 树形DP

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

void dfs(int u, int fa) {
    f[u] = w[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u); // 往下搜j点，并记录上一个点为u
        f[u] += max(0ll, f[j]);
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, -1);
    LL res = f[1];
    for (int i = 2; i <= n; i++) res = max(res, f[i]);
    printf("%lld\n", res);
    
    return 0;
}

旅游规划

树的直径，树形DP，节点记录

《信息学奥赛一本通》-旅游规划

树的直径：树上最远的两个节点之间的距离就被称为树的直径,连接这两点的路径被称为树的最长链。

本题就要求我们找出这样的最长链（可能有很多条），并将最长链上的节点全部输出

  1. 记录每个节点向下的最大值d1[]与次大值d2[]，及最大值的目标节点p1[]
  2. 记录每个节点向上的值up[]，从ii出发往上走的最大值为从uu出发不走ii的最大值+1+1
image-20220329171001231 
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
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 2e5 + 10, M = 2*N;
int n;
int h[N], e[M], ne[M], idx;
int d1[N], d2[N], up[N], p1[N]; // 最大距离，次大距离，往上走距离，最大值的点
int maxd; // 树的直径

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

void dfs_d(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        // core code
        if (j != fa) {
            
            dfs_d(j, u); // 自下而上更新
            int distance = 1 + d1[j];
            if (distance > d1[u]) { // 更新最大值与次大值
                d2[u] = d1[u], d1[u] = distance;
                p1[u] = j;
            } else if (distance > d2[u]) {
                d2[u] = distance;
            }
        }
    }
    
    maxd = max(maxd, d1[u] + d2[u]);
}
 // 从u出发往上走的最大值为1+从j出发不走u的最大值
void dfs_u(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        // core code
        if (j != fa) {
            up[j] = up[u] + 1; // 自上而下更新
            if (p1[u] == j) up[j] = max(up[j], d2[u] + 1);
            else up[j] = max(up[j], d1[u] + 1);
            dfs_u(j, u);
        }
    }
}
int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    dfs_d(0, -1);
    dfs_u(0, -1);
    
    for (int i = 0; i < n; i++) {
        int d[3] = {d1[i], d2[i], up[i]};
        sort(d, d + 3);
        if (d[1] + d[2] == maxd) printf("%d\n", i);
    }
    
    return 0;
}

记忆化搜索

滑雪

  • 状态表示f[i,j]f[i,j]：所有从(i,j)出发的最长路径
  • 状态计算：f[i,j]=max(f[i,j−1]+1,f[i,j+1]+1,f[i−1,j]+1,f[i+1,j]+1)f[i,j] = max(f[i,j-1]+1,f[i,j+1]+1,f[i-1,j]+1,f[i+1,j]+1)

枚举出上下左右的4个点，(i,j)由它们的最大值转移而来

如果一个点的dp[][]不为初始化值-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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int n, m;
int f[N][N], h[N][N];

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

int dp(int x, int y) {
    // 引用：v相当于f[x][y]
    int &v = f[x][y];
    
    // 利用了记忆化搜索过程中的结果
    if (v != -1) return v;
    
    // 无格可走，最小为1
    v = 1;
    
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        
        if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) 
            // 记忆化搜索
            v = max(v, dp(a, b) + 1);
    }
    
    return v;
}

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> h[i][j]; // 读入高度
    
    // 初始化状态为-1
    memset(f, -1, sizeof f);
    
    int res = 0;
    // 枚举每一个点，取最大值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = max(res, dp(i, j));
    
    cout << res << endl;
    
    return 0;
}

901.滑雪

参考资料

AcWing算法基础课，欢迎大家报名，强推噢！！！y总带你感受算法之美！