动态规划算法

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

using namespace std;
typedef long long ll;
const int N = 1010;
int n, m;
int f[N][N];
int w[N], v[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 = 1; 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]);
            }
        }
    }
    int res = 00;
    for (int i = 0; i <=m; i++)
    {
        res = max(res, f[n][i]);
    }
    cout << res << endl;
    return 0;
}

给定一堆物品，这些物品有自己对应的空间，和价值，问再一个背包空间有限的背包中，放入哪些物品能使的背包中放的物品的价值总和最大。
背包问题是dp动态规划的经典问题，其核心点在于列表，对于前n个物品，每当背包空间达到该物品能放置的最小值时，我们进行判断是否放入该物品，如果放入的话，就要事先留下该物品的空间，然后在剩下的空间中找当前空间下，的最佳放法，依次类推。
如果感到难以理解的话，就来看看这个视频：
【动态规划】背包问题_哔哩哔哩_bilibili

[纯手推！！！]动态规划背包问题汇总 01背包 完全背包 多重背包 二维数组 一维滚动数组_哔哩哔哩_bilibili

优化

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

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

（1）状态f[j]定义：N件物品，背包容量j下的最优解。

（2）注意枚举背包容量j必须从m开始。

（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i] [j]与f[i - 1] [j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

（4）例如，一维状态第i轮对体积为 3的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该是f[i - 1] [4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i] [4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1] [4]。

（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i]
关于状态f[j]的补充说明
二维下的状态定义f[i] [j]是前 i件物品，背包容量 j下的最大价值。一维下，少了前 i件物品这个维度，我们的代码中决策到第 i件物品（循环到第i轮），f[j]就是前i轮已经决策的物品且背包容量 j下的最大价值。
因此当执行完循环结构后，由于已经决策了所有物品，f[j]就是所有物品背包容量 j 下的最大价值。即一维f[j]等价于二维f[n] [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
#include<bits/stdc++.h>
using namespace std;
const int N =110;
int v[N], w[N], s[N];
int f[N];
int main()
{
    int n,m;
    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 k = 1; k <= s[i]; k++)
        {
            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;
}

多重背包问题进行了一个更深层次的提问，物品不再是只有一件或者无限多，而是我们进行人为进行规定，既然如此，在时间复杂度允许的前提下，我们就把规定个数的物品进行复制，相当与这些同样的物品我们把他们当作01背包进行依次挨个挨个的遍历。就能解决问题。

二进制优化

我们会发现一个问题，当一个物品的数足够大的时候我们无法遍历那么多次，这里我们就要想到二进制转化的优化方案，我们发现，如果把n 拆分成2^k的时候，从1~n中间的每一个数都可以用2^k来表示，而我们的遍历次序也就从O（n）变成了O（nlogn），这样就大大降低了我们的时间复杂度，此时我们把n个物品组合成logn个2^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
40

#include<bits/stdc++.h>
using namespace std;
const int N =2010, M = 12010;
int v[M], w[M];
int f[N];
int n,m;
int main()
{
    cin >> n >> m;
    int pos = 0;
    for(int i = 1; i <= n; i++)
    {
        int v1, w1, s;
        cin >> v1 >> w1 >> s;
        int k = 1;
        while(k <= s)
        {
            v[++pos] = v1 * k;
            w[pos] = w1 * k;
            s -= k;
            k *= 2;
        }
        if(s > 0)
        {
            v[++pos] = v1 * s;
            w[pos] = w1 * s;
        }
        
    }
    for(int i = 1; i <= pos; 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;
}

这个是代码表述，注意在处理最后一组数据的时候如果此时s还有剩余，记得把他剩下的部分也加入数组中。

完全背包问题

基础

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

using namespace std;
typedef long long ll;
const int N = 1010;
int n, m;
int f[N][N];
int w[N], v[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 = 1; 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]);
            }
        }
    }
    int res = 00;
    for (int i = 0; i <= m; i++)
    {
        res = max(res, f[n][i]);
    }
    cout << res << endl;
    return 0;
}

完全背包问题就是在背包问题的基础上，我们使得每一个物品都可以无限次的放入，因为可以无限次的放入，因此我们这里在更新状态的时候就直接从本行开始，（01背包是从上一行开始的）因为这样我们就可以在背包充足的时候无限次数的放入当前物品。
[纯手推！！！]动态规划背包问题汇总 01背包 完全背包 多重背包 二维数组 一维滚动数组_哔哩哔哩_bilibili

优化

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

using namespace std;
typedef long long ll;
const int N = 1010;
int n, m;
int f[N];
int w[N], v[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]);
        }
    }
    int res = 00;
    for (int i = 0; i <= m; i++)
    {
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

优化的过程与背包问题同理，也就是在满足j >= v[i]的时候，我们不断从同一行进行更新。如果不能理解就看看视频吧。

线性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
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], f[N];
int n;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if(a[j] < a[i])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

最长上升子序列就是给定一个序列，然后找到最长的单调递增的子序列，在DP中我们先找状态表示，也就是以第i个数结尾的最长子序列，然后每次更新状态的时候就不断计入上一个状态的最长子序列，当然如果前面的数大于第i个，那么我们就不考虑。也就是从最开头的数开始，到第i - 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 = 100010;
int n, a[N], q[N];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int len = 0;
    q[0] = -2e9;
    for(int i = 0; i < n; i++)
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = (l + r + 1) / 2;
            if(q[mid] < a[i])
                l = mid;
            else
                r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    cout << len << endl;
    return 0.;
}

当数据范围稍微增大之后我们就会发现，上面那个方法会超时，这种情况下我们可以考虑使用二分来优化代码，但是使用二分的一个重要条件就是单调，那么我们怎么才能得到单调的函数呢？

这里我们不妨猜想，如果假定一个数是当前的最长子序列，那么从第一个数开始遍历，我们会发现这个数如果比前面的数小的话，那么他所包含的最长子序列一定至少比第i个数小1，那么此时我们应该能找到最长的比当前数短的子序列，画图我们就能轻松发现，随着最长子序列的数量的不断增加，每一个长度对应的最后一个数一定呈单调递增，

这样就满足二分的两个条件，求临界值和绝对单调，此时我们就可以使用二分来找出比当前长度恰好少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
#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;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if(a[i] == b[j])
            {
                f[i][j] = f[i - 1][j - 1] + 1;
            }
            else
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    cout << f[n][m] << endl;
}

类似01背包问题，唯一不同的敌方就是每次更新一个点的时候，我们都要分别考虑这个点上面的点和下面的点，不能被左上角的点局限，在遍历的时候，去上和左最大的值，如果当前两个字符串恰好尾巴上的字符相等，那么就让左上方的点++。

如果无法理解文字的话，就来看看这个视频吧
[轻松掌握动态规划]5.最长公共子序列 LCS_哔哩哔哩_bilibili

最短编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
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);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

此题要找把a字符串变成b字符串得最少步骤，总共有三种操作类型，删除，添加和更改。

认真观察我们会发现这个题的状态表示其实和前面最长公共子序列的相差无几，也就是考虑前面的那个字符和当前字符的关系，然后进行分类考虑，是要删除还是添加还是更改，删除就是保证删掉这个数后的最后一个字符与b的最后一个字符相等。添加就是保证添加一个字符后最后一个字符与b相等，这里为了防止出现+1的情况（让式子都是-1）我们判断变化后的情况即可，最后就是更改，要考虑是否进行更改，判断依据就是当前最后一个数是否相等。

三角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
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int w[N][N], f[N][N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
                cin >> w[i][j];
    }
    for (int i = 1; i <= n; i++)
    {
        f[n][i] = w[n][i];
    }
    for (int i = n - 1; i; i--)
    {
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
        }
    }
    cout << f[1][1] << endl;
    return 0;
}

三角DP是一类和简单的问题，就是从三角形顶端开始往下遍历，找出每次经过点的总和的最大值，
从DP的角度来看，从上往下来找显然是麻烦的，因为在三角形的边界处，我们会发现一个子节点只对应一个父节点，因此在边界处我们需要进行特判，然鹅我们发现从下面开始遍历的话，每一个父节点都对应一个两个子节点，因此在这里我们就可以从下往上遍历，然后更新每一次的状态，是从左上来的还是从右上来的。

编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 15;
char str[N][M];
int f[M][M];
int n, m;
int dist(char str[], char s[])
{
    int cnt = 0;
    int la = strlen(str + 1), lb = strlen(s + 1);
    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] + 1, f[i][j - 1] + 1);
            if(str[i] == s[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);
        }
    }
    return f[la][lb];
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        scanf("%s", str[i] + 1);
    }
    while(m--)
    {
        char s[M];
        int k;
        cin >> s + 1 >> k;
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            if(dist(str[i], s) <= k)
            {
                res++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

这道题和最短编辑距离相似，其实也可以说是一模一样，就是把判断的数据变得更多了而已。

为此我们把判断最短距离的过程放到方程里面，然后开一个二维数组每次把需要判断的字符串放入函数中，如果满足最小距离小于K，就让答案++，除此之外也没有投什么了。

区间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
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int f[N][N], a[N], sum[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = a[i] + sum[i - 1];
    }
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = 1e8;
            for (int k = i; k < j; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}

区间DP中的状态表示的i，j不再代表两个具体的数字，而是一个区间，表示的是再这个区里面，代价的最小值，

这道题通过细微的观察我们会发现，题目所要求的两两组合，说明组合的一定是左边一堆右边一堆，那么此时我们就可以找一个中间值来求当前的状态值，然后再不断遍历，直到最终找到那个最小的代价。

整形划分

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 1011, mod = 1e9 + 7;
int f[N];
int n;
int main()
{
    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] << endl;

    return 0;
}

第一类方法就把他当成是完全背包的类型来看，也就是说，把每一个数字都当成一件物品，然后没一个物品可以放无数多次，然后我们会发现状态更新时呈现
f [ i ] [ j ] = f [ i - 1 ] [ j - 1 ] + f [ i ] [ j - i ] 。
然后往下类推即可。
实在想不到的话再看看视频，多看两遍

思维

第二种解法更考验思维能力，一般来说很难想到。主要就是 用f [ i ] [ j ] 表示总和为 i 的情况下1 ~ j的组成 i 的个数。
我们把所有集合中，最小值是1的分成一类，然后把最小值不是1的分成一类，然后更新状态的时候，最小值是1的所有更新成 f [ i - 1 ] [ j - 1 ] 。相当于减掉一个最小值。然后把所有最小值不是1的情况更新成 f [ i - j ] [ j ] 。相当于是把所有数剪掉一个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
#include<bits/stdc++.h>
using namespace std;
const int N = 1011, mod = 1e9 + 7;
int f[N][N];
int 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 ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = (ans + f[n][i]) % mod;   
    }
    cout << ans << endl;

    return 0;
}

树形DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int N =6010;
int h[N], e[N], idx = 0, ne[N];
int w[N], cnt[N];
int f[N][2];
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dp(int u)
{
	f[u][1] = w[u];
	f[u][0] = 0;
	for(int i = h[u]; i != -1; i = ne[i])
	{
		int v = e[i];
		dp(v);
		f[u][0] += max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
	}
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> w[i];
	}
	memset(h, -1, sizeof h);
	for(int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		add(v,u);
		cnt[u]++;
	}
	int gen = 0;
	for(int i = 1; i <= n; i++)
	{
		if(cnt[i] == 0)
		{
			gen = i;
			break;
		}	
	}
	dp(gen);
	int res = max(f[gen][0], f[gen][1]);
	cout << res << endl;
	return 0;
}

此题名为没有上司的舞会，在一个树当中，若选择一个点则不能选择与他相邻的所有点，每个点有对应的权值，最后计算总和的最大值。

在树形DP中我们需要先找到根节点，然后进行DP，状态表示为是否选择当前的节点，如果选择那么就不能选相邻的节点，如果不选择可以选择或者不选择相邻的节点。注意在建立邻接表的时候要初始化表内的值，防止出问题，然后再存入树的时候因为后面的数是前面的数的上司，因此在存的时候要反着来。

这里还有状态压缩DP等难度较大的动态规划问题，我暂时还没有理解，感兴趣的话可以去看看一些大佬的状压DP