acwing算法笔记-动态规划

背包问题

背包问题的本质：给我们一堆物品，每个物品有体积v有价值w，有各种限制，背包装的下地前提下，最多能装多少（背包不一定装满）

  1. 01背包问题：每件物品最多只能用一次
  2. 完全背包：每件物品可以用无限次
  3. 多重背包：每件物品的数量不一样
  4. 分组背包：物品有n组，每一组有若干个

背包问题的思路

  1. dp问题，一般就是两步，状态表示和状态计算

  2. 状态表示 f(i,j) 表示集合的某种属性

  • 集合：所有选法（条件限制：只从前i个物品中选，总体积 <= j）
  • 属性：常见的有max, min, 数量（属性是一个值，集合里每种选法存储的值）
  1. 状态计算其实就是集合的划分，当前的集合分为哪些类，然后根据属性得到f(i,j)的状态转移方程

dp的优化和分析是分开的，我们一般先把朴素做法分析完后，再优化
优化其实就是对常规dp的代码或者方程做一个等价的变形
dp是一种思想，不存在固定的模板

2. 01背包问题

基本思路

对于N件物品，每件物品都有选or不选两种情况，因此总共有2^N种情况，我们将这看作一个集合，然后找到集合里最大值的情况。

  1. 如果用DFS来做的话，当然也是可以的，但是复杂度显然是指数级别的。
  2. 有限集合里的最优解问题，可以考虑用DP来做

所以DP问题两步走

  1. 状态表示：f(i,j))的定义是什么?
    两个方面，首先对应的集合是什么：从前i个物品里选，且总体积不超过j的选法集合
    然后就是我们所关注的是集合里的什么属性（集合里每种选法存的是什么值）：这里关注的是最大值，也就是集合里存储的是每种方案的最大值。
    所以f(i,j)的定义就是从前i个物品里选，且总体积不超过j的选法集合中的最大值

  2. 状态计算
    把集合进行划分，得到状态转移方程，怎么划分（这里是找到最后一个物品选还是不选）
    分成两部分，一部分是不选第i物品的方案，另一部分是包含第i物品的方案，然后两部分取max，所以状态转移方程f(i, j) = max(f(i - 1, j) + f(i - 1, j - v(i)) + w(i))

  3. 滚动数组优化

  • 优化这里我们发现i只依赖于i-1，所以可以通过滚动数组优化空间，常见的方式有取模或者&

  1. 二维优化到一维
    首先我们发现i只和i - 1有关，所以可以去掉i，优化成一维。然后对于j，我们是小（j -vi) 更新大(j) ，所以如果是正序，大的更新的时候，小的已经先被更新，那么两边都是第i轮；
    如果是倒序，大的更新的时候，小的还没有被更新，大的是第i轮，小的是第i - 1轮；这里我们需要的是i - 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//版本1：朴素做法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N]; //每个物品的体积
int w[N]; //每个物品的价值
int f[N][N]; //状态转移方程，上面有详细解释
int main(){
    int n,m;
    scanf("%d%d",&n,&m); //输入物品数量和背包容量
    for(int i = 1;i <= n;i ++) scanf("%d%d",&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]); //合法时的状态计算
        }
    }
    printf("%d",f[n][m]); //输出答案
    return 0;
}

//版本2：朴素做法合并if else
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N]; //每个物品的体积
int w[N]; //每个物品的价值
int f[N][N]; //状态转移方程，上面有详细解释
int main(){
    int n,m;
    scanf("%d%d",&n,&m); //输入物品数量和背包容量
    for(int i = 1;i <= n;i ++) scanf("%d%d",&v[i],&w[i]); //输入每个物体的体积和价值
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= m;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]); //右子集不一定存在（不一定合法，所以要限制条件使其合法）
        }
    }
    printf("%d",f[n][m]);
    return 0;
}


//版本3：滚动数组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N];
int w[N];
int f[2][N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d%d",&v[i],&w[i]);
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= m;j ++){
            f[i & 1][j] = f[i - 1 & 1][j];
            if(j >= v[i]) f[i & 1][j] = max(f[i & 1][j],f[i - 1 & 1][j - v[i]] + w[i]);
        }
    }
    printf("%d",f[n & 1][m]);
    return 0;
}

//版本4：一维数组
#include <iostream>
#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 = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

Reference

[1]. yxc
[2]. 01背包问题代码优化完全详解
[3]. 01背包问题 简要思路)
[4]. 二维到一维详解
[5]. 以01背包为例, 归纳总结算法导论中动态规划的解题步骤并深度探索原理和推广


3. 完全背包问题

基本思路

01背包问题的变形，还是用动态规划来做

动态规划两步走

  1. 状态表示f(i,j), 它表示的是前i个物品，总体积不大于j的所有选法集合中的最大值

  2. 状态计算
    这里集合划分，我们之前01背包问题是根据最后一个物品选or不选分成两部分
    这里我们第i个物品可以选无限多个，所以可以划分成0~k个子集（直到不能选为止）
    f[i][j] = max(f[i-1][j] + f[i-1][j- v] + w + f[i-1][j-2v] + 2w + …])

  3. 优化
    先优化时间复杂度，最后一层枚举k，总共三层for循环，时间复杂度很高，所以这里我们要对状态方程进行化简
    最后发现通过

    1
    2
    3
    f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w ...)
    f[i][j-v] = max(f[i-1][j-v] + f[i-1][j-2v] + w ...)
    简化方程为 f[i][j] = max(f[i-1][j], f[i][j-v] + w)

然后优化空间复杂度，因为i只依赖于i-1，所以可以滚动数组优化，然后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
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
83
84
85
86
87
88
89
90
91
92
//版本1 状态转移方程未优化
#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(){
    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 <= j / v[i];k ++){  //k * v[i] <= j 限制，一定合法
                f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}


//版本2 滚动数组优化空间
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[2][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 <= j / v[i];k ++){
                f[i & 1][j] = max(f[i & 1][j],f[i - 1 & 1][j - v[i] * k] + w[i] * k);
            }
        }
    }
    cout<<f[n & 1][m]<<endl;
    return 0;
}


//版本3 状态转移方程优化
#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(){
    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 ++){
            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][m]<<endl;
    return 0;
}

//版本4 一维空间优化
#include <iostream>
#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;
}

Reference

[1]. yxc
[2]. 完全背包问题（良心正解）


4. 多重背包问题I

基本思路

和完全背包的朴素做法几乎一样，唯一区别就是完全背包每件物品可以用无限次，而多重背包每件物品只能用有限次。

注意：

  1. 状态计算时，k属于[0, s[i]]，所有子集并不一定合法，所以需要限制条件，使其合法。 条件就是 k * v[i] <= j
  2. 这里因为数据量小，所以可以用三重循环的朴素做法，数据量大的时候，会TLE

参考代码

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 <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

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;
}

Reference

[1]. yxc
[2]. 多重背包问题I（良心正解）


5. 多重背包问题II

基本思路

多重背包2这里增大了数据范围，所以朴素做法会超时，所以我们尝试优化状态转移方程，发现由于si个数的限制，无法像完全背包问题一样优化状态转移方程
所以这里我们采取另一种优化思路：二进制拆分
朴素做法里需要枚举k个数，这里我们将k进行二进制拆分 拆成logk（上取整）个数，每个数分别是$2^0, 2^1, 2^(logk - 1)$. 然后任意的k我们都可以用这些数通过选or不选得到
所以就转化成了01背包问题

注意：

  1. 完全背包问题和多重背包问题其实有两种理解：这两种模型其实是等价的
  • i件物品，每件物品可以用无限次（完全背包）或者s次（多重背包）
  • i种物品，每种物品有无数个（完全背包）或者s个（多重背包)

我们之前都是基于第一种理解，总共n件物品，所以v，w数组大小是n，然后直接每件物品读入w，n数组；
但是如果涉及到拆分的话，其实就是第二种理解，物品总数大约是n * s种（为什么是大约，因为不同种类物品，个数不同）所以v，w数组大小是n * s，然后我们在每种物品里相当于把s件拆成了log s件，所以物品件数，v,w数组大小缩小至n*logs

  1. 转化为01背包问题后，需要优化到一维，否则会数组过大导致内存溢出MLE

参考代码

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
#include<iostream>

using namespace std;

const int N = 11 * 1000 + 10, M = 2010;

int  n, m;
int v[N], w[N];
int f[M];

int main()
{
    
    cin >> n >> m;

    int cnt = 0;     // 拆分后的物品总数量
    for (int i = 1; i <= n; i ++)   //遍历每种物品
    {
        int a, b, s;    // 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;  // 物品总数量 =  01背包中的物品个数

    // 做一遍01背包问题，注意一定要转化为一维
    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;
}

Reference

[1]. yxc
[2]. 优化方法详解


9. 分组背包问题

基本思路

与完全背包问题的唯一区别，就是完全背包是第i个物品选几个，而分组背包是第i个物品选哪个。

参考代码

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
版本1 朴素版
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;

int f[N][N];
int v[N][N], w[N][N], s[N];
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> s[i];//第i组物品的数量
        for(int j = 1; j <= s[i]; j ++){//依次读入第i组第j个物品的体积和价值
            cin >> v[i][j] >> w[i][j];
        }
    }

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            f[i][j] = f[i - 1][j];//第i组物品一个都不选
            for(int k = 1; k <= s[i]; k ++){
                if(j >= v[i][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;
}

版本2 优化一维数组
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[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;
}

Reference

[1]. AcWing 9. 分组背包问题
[2]. AcWing 9. 分组背包问题
[3]. AcWing 9. 分组背包问题（良心正解）


数字三角形问题

898. 数字三角形

基本思路

这道题目首先考虑有多少种选法，$2^{n-1}$种选法，然后选出最优解，如果用DFS爆搜的话，结合数据范围必然会超时，所以我们采用DP的方法。

DP问题两步走

  1. 状态表示：i表示行，j表示列（这里是三角形，所以j可以理解为该行的第几个 = 列）
    这里可以从上到下看，也可以从下到上看，这里我们先讨论从上到下看
    f[i][j]的定义就是从（1，1）到（i，j)的所有路径的最大值

  2. 状态计算
    这里我们进行集合的划分，可以发现（i，j）只能从左上方or右上方走到该点
    所以集合可以划分为两部分，然后得到状态转移方程f[i][j]=max(f[i-1][j-1],f[i-1][j])
    最后枚举最后一层元素，取f的最大值即可

    这里要注意 三角形两边的元素没有左上/右上元素，需要把没有元素的地方数字置为负无穷

或者我们可以从下往上看

  1. 状态表示 f[i][j]的定义就是从（i，j）到（1，1)的所有路径的最大值

    这样的话不用考虑边界问题，也不用枚举最后一层才可以得到答案,代码会简洁一些

  2. 状态计算
    也是集合划分为两部分，从左下角or右下角走到该点（i，j)
    所以状态转移方程f[i][j]=max(f[i+1][j],f[i+1][j+1])，最后我们求解的就是f(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
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
版本1 从上到下
#include <iostream>
using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];    //三角型
int f[N][N];    //状态表示

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)        //输入三角形
        for(int j=1;j<=i;j++)
            cin>>a[i][j];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=i+1;j++)  //初始化f
            f[i][j] = -INF; 

    f[1][1] = a[1][1];           //初始化起点
    for(int i=2;i<=n;i++)        //状态转移，计算所有的f
        for(int j=1;j<=i;j++)
            f[i][j] = max(f[i-1][j],f[i-1][j-1]) + a[i][j];

    int res = -INF;    
    for(int i=1;i<=n;i++)        //在最后一行选终点（选最大的f）    
        res = max(res,f[n][i]);

    cout<<res<<endl;
    return 0;
}

版本2 从下到上
#include <iostream>
using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];    //三角型
int f[N][N];    //状态表示

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)        //输入三角形
        for(int j=1;j<=i;j++)
            cin>>a[i][j];

    for(int i=1;i<=n;i++) f[n][i] = a[n][i];   //初始化起点

    for(int i=n;i>=1;i--)        //状态转移，计算所有的f
        for(int j=i;j>=1;j--)
            f[i][j] = max(f[i+1][j],f[i+1][j+1]) + a[i][j];

    cout<<f[1][1]<<endl;       //终点只要一个，答案即f[1][1]

    return 0;
}

Reference

[1]. AcWing 898. 数字三角形
[2]. AcWing 898. 数字三角形
[3]. AcWing 898. 数字三角形的正序解法, 倒序解法, 正序的空间复杂度优化(二维转一维滚动数组)

tips: 如何计算动态规划的时间复杂度，就是用状态数 * 状态计算的时间复杂度，这里状态数是O(N^2),计算是O(1)。然后一个题目的数据范围非常重要，我们可以通过数据范围推测大概能用的算法


最长上升子序列问题

895. 最长上升子序列1

最优问题，动态规划，DFS，因为数据范围是1000，所以显然用DFS大概率超时，所以选择动态规划

基本思路

动态规划两步走

  1. 状态表示，这里可以不需要二维了，直接一维f(i)定义为以i结尾的所有上升子序列的最大值

  2. 状态计算，怎么划分集合呢，一般观察最后一步，最后一步就是倒数第二个数，所以可以根据倒数第二个数划分（枚举倒数第二个数），如果合法就得到状态转移方程f[i] = max(f[i], f[j] + 1)

参考代码

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 a[N]; //输入用的数组
int f[N]; //用来存储每个答案，在最后要for循环遍历找最大值（被坑了）
int main(){
    int n; //字符个数
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++){
        f[i] = 1; //付初值。即使这个数后面没有比它大的数，它本身也算一个
        for(int j = 1;j <= i;j ++){
            if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1); //如果这个数大于前面那个数，说明是合法的，把它等于max(f[i],f[j] + 1)
        }
    }
    int res = -0x3f3f3f3f; //最长上升子序列的答案，因为a数组中的数字有可能为负数，所以要付成很小的数
    for(int i = 1;i <= n;i ++) res = max(res,f[i]); //找最大值~
    printf("%d\n",res); //输出最后答案~
    return 0;
}

Reference

[1]. AcWing 895. 最长上升子序列
[2]. AcWing 895. 最长上升子序列


897. 最长公共子序列问题

基本思路

dp两步走

  1. 状态表示 f(i,j)定义为所有a[1..i]和b[1…j]的公共子序列集合的最大值

  2. 状态计算 这里还是按照最后一步去集合划分，是否包含i和j，分成四种情况，00，01，10，11。其中要注意01，10，他不是简单的等价于f(i-1, j)和f(i, j -1)，因为f(i-1, j)结果里j不一定出现，但是01的话j一定出现，所以f(i-1, j)实际上是包含了01这种情况，10也是同理，由于我们求得是max而不是数量，所以只需要做到不漏，不需要做到不重复，得到状态转移方程：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)

参考代码

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;

int n , m;
char a[N] , b[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    cin >> 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]);//01和10的情况一定存在，所以可以无条件优先判断
                if(a[i] == b[j]) f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);
            }                                                       

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

Referenece

[1]. AcWing 897. 最长公共子序列
[2]. AcWing 897. 最长公共子序列
[3]. AcWing 897. 最长公共子序列


区间DP问题

282. 石子合并

基本思路

DP问题两步走

  1. 状态表示 f(i,j)定义的是所有将[i,j]合成一堆的方案的集合的最小值

  2. 状态计算 如何划分集合，这里还是看最后一步，最后一步是两个堆合并，左边的堆可以是[i, k], k属于[i, j - 1]，所以根据这个进行集合的划分，得到状态转移方程：f[l][r] = min(f[l][r],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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n;
int s[N]; //1~k的石子个数累加起来，也就是前缀和
int f[N][N];
int main(){
    cin>>n;
    for(int i = 1;i <= n;i ++){ //读入每堆石子的个数（合并代价）
        cin>>s[i]; //读入第i堆石子的个数（合并代价）
        s[i] += s[i - 1]; //计算前缀和，具体见注释①
    }
    for(int len = 2;len <= n;len ++){ //见注释②
        for(int i = 1;i + len - 1 <= n;i ++){ //枚举左端点
            int l = i,r = i + len - 1; //现在我们就可以通过左端点找到右端点
            //l为左端点（弄这个数字其实是为了好看），r为右端点
            f[l][r] = 0x3f3f3f3f; //要求最小值，所以要把这个数赋值为+∞，如果不赋值的话答案会等于0
            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;
}

Reference

[1]. AcWing 282. 石子合并
[2]. AcWing 282. 石子合并
[3]. AcWing 282. 石子合并


数位DP问题

y总翻车了…，之后提高课总综合一起写

338. 计数问题


状态压缩DP问题

291. 蒙德里安的梦想问题

基本思路

太复杂了，我自己是不太好总结了，多看看别人的消化一下把…
[1]. ShizhengLee
[2].蒙德里安的梦想（大佬们写的都挺完整的，做一个补充）
[3]. AcWing 291. 本题关键点总结
[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
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
#include<iostream>
#include<cstring>

using namespace std;

//数据范围1~11
const int N = 12;
//每一列的每一个空格有两种选择，放和不放，所以是2^n
const int M = 1 << N;
//方案数比较大，所以要使用long long 类型
//f[i][j]表示 i-1列的方案数已经确定，从i-1列伸出，并且第i列的状态是j的所有方案数
long long f[N][M];
//第 i-2 列伸到 i-1 列的状态为 k ， 是否能成功转移到 第 i-1 列伸到 i 列的状态为 j
//st[j|k]=true 表示能成功转移
bool st[M];
//n行m列
int n, m;

int main() {
//    预处理st数组
    while (cin >> n >> m, n || m) {
        for (int i = 0; i < 1 << n; i++) {
//            第 i-2 列伸到 i-1 列的状态为 k ， 
//            能成功转移到 
//            第 i-1 列伸到 i 列的状态为 j
            st[i] = true;
//            记录一列中0的个数
            int cnt = 0;
            for (int j = 0; j < n; j++) {
//                通过位操作，i状态下j行是否放置方格，
//                0就是不放， 1就是放
                if (i >> j & 1) {
//                    如果放置小方块使得连续的空白格子数成为奇数，
//                    这样的状态就是不行的，
                    if (cnt & 1) {
                        st[i] = false;
                        break;
                    }
                }else cnt++;
//                不放置小方格
            }

            if (cnt & 1) st[i] = false;
        }

//        初始化状态数组f
        memset(f, 0, sizeof f);

//        棋盘是从第0列开始，没有-1列，所以第0列第0行，不会有延伸出来的小方块
//        没有横着摆放的小方块，所有小方块都是竖着摆放的，这种状态记录为一种方案
        f[0][0] = 1;
//        遍历每一列
        for (int i = 1; i <= m; i++) {
//            枚举i列每一种状态
            for (int j = 0; j < 1 << n; j++) {
//                枚举i-1列每一种状态
                for (int k = 0; k < 1 << n; k++) {
//                    f[i-1][k] 成功转到 f[i][j]
                    if ((j & k) == 0 && st[j | k]) {
                        f[i][j] += f[i - 1][k]; //那么这种状态下它的方案数等于之前每种k状态数目的和
                    }
                }
            }
        }
//        棋盘一共有0~m-1列
//        f[i][j]表示 前i-1列的方案数已经确定，从i-1列伸出，并且第i列的状态是j的所有方案数
//        f[m][0]表示 前m-1列的方案数已经确定，从m-1列伸出，并且第m列的状态是0的所有方案数
//        也就是m列不放小方格，前m-1列已经完全摆放好并且不伸出来的状态
        cout << f[m][0] << endl;
    }
    return 0;
}

91. 最短Hamilton路径

基本思路

状态压缩dp问题，就不写自己的了hh
[1]. yxc
[2]. 冰中月
[3]. 最短Hamilton路径（管家级详解）
[4]. 垫底抽风
[5]. Bug-Free

参考代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20,M = 1 << N;
//解释一下1 << N：因为i是二进制数，表示从0到当前点的状态，所以每个点都有两个状态0和1，所以是2的N次方
int n;
int w[N][N]; //每条边的权重
int f[M][N]; //表示从0到j，走过的点是i的所有路径
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < n;j ++){
            scanf("%d",&w[i][j]);
        }
    }
    memset(f,0x3f,sizeof f);
    f[1][0] = 0; //0为起点，所以为0
    for(int i = 0;i < 1 << n;i ++){ //i表示的所有的状态
        for(int j = 0;j < n;j ++){ //j表示走到的哪一点
            if(i >> j & 1){ //如果i的j为1，说明到达过这个点
                for(int k = 0;k < n;k ++){ //k表示走到j这个点之前，以k为终点的最短距离
                    if((i - (1 << j)) >> k & 1){ //i除去j这个点后包含k这个点
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]); //状态转移，前面图1有详细讲解哦~
                    }
                }
            }
        }
    }
    printf("%d\n",f[(1 << n) - 1][n - 1]); //输出答案
    //(1 << n) - 1表示：有n个1，也就是所有的点都走完了
    //n - 1表示：终点
    //合起来就是所有的点都走完的方案，最后落脚在n - 1这个点
    return 0;
}

树形DP问题

285. 没有上司的舞会

基本思路

[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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; //上面有解释哦~
int e[N],ne[N],h[N],idx; //链表，用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点
void add(int a,int b){ //把a插入树中
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u){ //开始求解题目
    f[u][1] = happy[u]; //如果选当前节点u，就可以把f[u,1]先怼上他的高兴度
    for(int i = h[u];~i;i = ne[i]){ //遍历树
        int j = e[i];
        dfs(j); //回溯
        //状态转移部分，上面有详细讲解~
        f[u][0] += max(f[j][1],f[j][0]);
        f[u][1] += f[j][0];
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&happy[i]); //输入每个人的高兴度
    memset(h,-1,sizeof h); //把h都赋值为-1
    for(int i = 1;i < n;i ++){
        int a,b; //对应题目中的L,K,表示b是a的上司
        scanf("%d%d",&a,&b); //输入~
        has_father[a] = true; //说明a他有爸爸（划掉）上司
        add(b,a); //把a加入到b的后面
    }
    int root = 1; //用来找根节点
    while(has_father[root]) root ++; //找根节点
    dfs(root); //从根节点开始搜索
    printf("%d\n",max(f[root][0],f[root][1])); //输出不选根节点与选根节点的最大值
    return 0;
}


记忆化搜索DP

901. 滑雪

基本思路

[1]. 滑雪（良心正解）
[2]. 滑雪—闫式dp分析法分析：一种更容易理解的思路+图解
[3]. Bug-Free

参考代码

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 <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n,m; //网格滑雪场的行和列
int f[N][N]; //状态转移式
int h[N][N]; //网格滑雪场
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int x,int y){
    int &v = f[x][y]; //Y总说的小技巧，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化
    if(v != -1) return v; //如果已经计算过了，就可以直接返回答案
    v = 1; //注意v要先赋值为1哦~
    for(int i = 0;i < 4;i ++){ //四个方向
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走
            v = max(v,dp(xx,yy) + 1); //更新
        }
    }
    return v; //别忘了返回v啊（被坑了
}
int main(){
    cin>>n>>m; //输入滑雪场行和列
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin>>h[i][j]; //读入滑雪场数据
        }
    }
    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;
}

算法 > AcWing
#算法 #动态规划
acwing算法笔记-动态规划
https://vendestine.com/dp-basic
Author
Wenzhe Li
Posted on
May 10, 2022
Licensed under