0%

算法基础（15）

发表于 更新于 分类于 本文字数： 9.1k
线性DP，区间DP

线性DP

线性DP是指状态转移的递推方程有明显的线性关系，有一维线性或二维线性。

1.数字三角形

例题1：数字三角形（Acwing 898）

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

数据范围：$1≤n≤500, −10000≤$三角形中的整数$≤10000$。

  • 状态表示$f[i,j]$：
    • 集合：所有从起点走到$(i,j)$的路径
    • 属性：Max，所有路径上的数字之和的最大值
  • 状态计算：
    • 把所有从起点到当前点$(i,j)$的路径分成两类，一类是从当前点左上方来的，可以用$f[i-1,j-1]+a[i,j]$来表示；一类是从右上方来的，可以用$f[i-1,j]+a[i.j]$来表示；
    • 则状态转移方程为：$f[i,j]=\max(f[i-1,j-1], f[i-1,j])+a[i,j]$。

关于DP问题代码下标的小Tip：若涉及到i-1这种下标，那让i>=1，即下标从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
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
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 = 0; i <= n; i ++)
        for(int j = 0; j <= i + 1; j ++)   //注意初始化时遍历列，要到i+1
            f[i][j] = -INF;    //先将f[i][j]初始化为负无穷
    
    f[1][1] = a[1][1];
            
    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
    
    int res = -INF;
    for(int j = 1; j <= n; j ++)     //遍历最底层找到最大值
        res = max(res, f[n][j]);
        
    cout << res << endl;
    
    return 0;
}

有一点需要注意，在初始化f[i][j]为负无穷的时候，在每一行中遍历时要多初始化一个，即j<=i+1。因为枚举到每行最右边的数时，它的最大值要看它左上和右上两个数，其右上的数在a[][]中不存在，但是其状态我们会用到，所以也必须初始化为负无穷；如枚举到f[2][2]，其右上的数为f[1][2]，因此在初始化i=1行时，要初始化f[1][1]和f[1][2]，即j<=i+1。

2.最长上升子序列（LIS）

例题2：最长上升子序列（Acwing 895）

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

如数列$3,1,2,1,8,5,6$，最长上升子序列可以取$1,2,5,6$，长度为4。

数据范围：$1≤N≤1000，−10^9≤$数列中的数$≤10^9$。

  • 状态表示f[i]：
    • 集合：所有以第i个数结尾的上升子序列；
    • 属性：Max，集合中每一个上升子序列的长度的最大值
  • 状态计算：
    • 集合的划分：以$a_i$结尾的上升子序列可以按其前一个数$a_j$来分，即按其前一个上升子序列的结尾来分，按$a_j$是第0个数，第1个数，第2个数，……，第$i-1$个数来分，当然这些分的情况并不一定存在，必须要满足$a_j<a_i$；
    • 则状态转移方程为：$f[i]=\max(f[j]+1)$，其中$j=0,1,2,\dots,i-1$。时间复杂度为$O(n\cdot n)=O(n^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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int n;
int a[N], f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;  //以a[i]结尾的上升子序列至少有a[i]一个数
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}

如果不仅想求最长子序列的长度，还要输出所求的最长子序列是什么，则可以用一个数组把“状态转移记住”，即保存让f[i]更新的那个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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 1010;
int n;
int a[N], f[N], g[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;  //以a[i]结尾的上升子序列至少有a[i]一个数
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                if(f[i] < f[j] + 1)
                {
                    f[i] = f[j] + 1;
                    g[i] = j;   //g[i]存的是i的状态是从j转移来的
                }
    }
    
    int k = 1; 
    for(int i = 1; i <= n; i ++)
        if(f[k] < f[i])
            k = i;
            
    cout << f[k] << endl;   //f[k]即是最长子序列的长度
    
    vector<int> LIS;
    for(int i = 0, len = f[k]; i < len; i ++)
    {
        LIS.push_back(a[k]);
        k = g[k];      //现在是倒着存的，之后需要翻转一下
    }
    
    reverse(LIS.begin(), LIS.end());
    
    for(auto c : LIS)  cout << c << ' ' ;
    
    cout << endl;
    
    return 0;
}

例题3：最长上升子序列II（Acwing 896）

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

数据范围：$1≤N≤100000，10^9≤$数列中的数$≤10^9$。

例题3和例题2的区别是，数列长度N的范围变大了，为10万，若用题2的代码，时间复杂度为$O(n^2)$，$100000^2=10^{10}$，则会超时，因此需要在题2的代码上做优化，可以优化到$O(n \log n)$。

之前的思路是：分别求以每个数字结尾的最长上升子序列的长度。考虑每次求的时候有没有冗余：对于样例$3,1,2,1,8,5,6$，考虑长度为1的子序列，若第$i$个数可以接到3后面，那一定可以接到第二个数$1$后面，那3就没有必要存了，因为1比3小，适用范围更广。

一般地，在长度为$k$的子序列中，我们只需存结尾的数最小的那个子序列。那我们可以把数$a_i$前面这些所有不同长度的上升子序列结尾的最小值存到一个数组q[]，可证明这些上升子序列的长度越长，其结尾的数越大，即这个数组q[]是严格单调递增的。

若求以$a_i$结尾的最长上升子序列，因为$a_i$可以接到比自己小的数的末尾，因此要在数组中找到最大的小于$a_i$的数，不妨设是q[4]，$a_i$接到其后面长度就是5；又因为q[5] >= a[i]，所以a[i]一定不可能接到一个长度大于等于5的LIS后面，因此以a[i]结尾的LIS的长度最大是$4+1=5$。做完这步之后要更新q[5]=a[i]。

如何在有序序列q[]中找到小于a[i]的最大的数？用简单的二分就可以了，时间复杂度为$O(\log n)$，因此算法总的时间复杂度为$O(n \log 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
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int n;
int a[N], q[N];   //存所有不同长度的上升子序列的结尾的最小值

int main()
{
    scanf("%d", &n);
    
    for(int i = 0; i < n; i ++)
        scanf("%d", &a[i]);
    
    int len = 0;     //存当前找到的最长上升子序列的长度
    q[0] = -2e9;     //当作哨兵，一定小于所有的a[i]
    for(int i = 0; i < n; i ++)
    {
        int l = 0, r = len;    //套用二分模板即可
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i])  l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);    //r是找到a[i]该接哪的末尾，因此LIS的长度就是r+1
        q[r + 1] = a[i];
    }
    
    printf("%d\n", len);
    
    return 0;
}

3.最长公共子序列（LCS）

例题4：最长公共子序列（LCS）（Acwing 897)

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

数据范围：$1 \le N, M \le 1000$

如字符串acbd和abedc的最长公共子序列是abd。

  • 状态表示f[i,j]：
    • 集合：所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现的子序列
    • 属性：Max，最长的公共子序列
  • 状态计算：
    • 以a[i]和b[j]是否出现在子序列中，来划分集合；a[i]和b[j]是否出现在子序列中有四种情况：00表示都不选，01表示只选b[j]，10表示只选a[i]，11表示都选（要求a[i]=b[j]）。f[i,j]表示的所有公共子序列一定可以不重不漏的分到这四种情况当中，f[i,j]的最大值就是这四种情况的最大值再取max
    • 00——f[i-1][j-1]，11——f[i-1][j-1]+1，中间两种情况比较难表示，如01不能简单地用f[i-1][j]来表示，因此f[i-1][j]不一定包含b[j]，但f[i-1][j]是严格包含01这种情况的，那f[i-1][j]的最大值是大于等于01集合的最大值的，那在计算集合最大值时就能用f[i-1][j]来代替01，同理可以用f[i][j-1]来代替10。这样做还有个好处：00——f[i-1][j-1]这种情况是包含在f[i-1][j]$$\cup$$f[i][j-1]中的，因此只需计算三种情况：f[i-1][j]，f[i][j-1]，f[i-1][j-1]+1。
    • 则状态转移方程为：$f[i,j=\max(f[i-1,j],f[i,j-1],f[i-1,j-1]+1)$，时间复杂度为$O(n^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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", 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);
        } 
        
    printf("%d\n", f[n][m]);
    
    return 0;
}

4.编辑距离

例题5：最短编辑距离（Acwing 902）

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

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

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

数据范围：$1≤n,m≤1000$

  • 状态表示f[i,j]：
    • 集合：所有将a[1~i]变成b[1~j]的操作方式
    • 属性：Min，所有操作方式的操作次数的最小值
  • 状态计算：
    • 类似的思路，我们以最后一步采用了什么操作将集合f[i,j]划分为三个子集：
      1. 若最后一步是删除操作，即删除了a[i]后，a[1~i-1]与b[1~j]相等，则这一子集的操作数为f[i-1,j]+1；
      2. 若最后一步是插入操作，即a[i]后插入一个数后，a[1~i+1]与b[1~j]相等，则之前是a[1~i]与b[1~j-1]相等，则这一子集的操作数为f[i,j-1]+1；
      3. 若最后一步是修改操作，即a[i]修改后，a[1~i]与b[1~j]相等，则之前是a[1~i-1]与b[1~j-1]相等，则这一子集的操作数为f[i-1,j-1]+1（a[i]!=b[j]，需要修改），或f[i-1,j-1]（a[i]=b[j]，不需要修改）；
    • 则状态转移方程为：$f[i,j]=\min(f[i-1,j]+1,\, f[i,j-1]+1,\, f[i-1,j-1]+1/0)$，时间复杂度为$O(n^2)$（状态数为$n^2$，每次状态转移计算量为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
#include<iostream>
#include<algorithm>
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;  //若要把a[]的前0个字母变成b[]的前i个字母，就要插入i次
    for(int i = 0; i <= n; i ++)  f[i][0] = i;  //若要把a[]的前i个字母变成b[]的前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;
}

例题6：编辑距离（Acwing 899）

给定n个长度不超过10的字符串以及m次询问，每次询问给出一个字符串和一个操作次数上限。对于每次询问，请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串，每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

数据范围：$1≤n,m≤1000$。字符串中只包含小写字母，且长度均不超过10。

这道题其实就把最短编辑距离重复若干次。

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>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 12, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_dis(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
    for (int i = 0; i <= la; i ++ ) f[i][0] = 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);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    return f[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1);

    while (m -- )
    {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i ++ )
            if (edit_dis(str[i], s) <= limit)
                res ++ ;

        printf("%d\n", res);
    }

    return 0;
}

2.区间DP

例题7：石子合并（Acwing 282）

设有N堆石子排成一排，其编号为1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有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。

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

数据范围：$1 \le N \le 300$。

区间DP问题在考虑状态表示时是用某一个区间。

  • 状态表示f[i,j]（第i堆石子到第j堆石子这个区间）：
    • 集合：所有将第i堆到第j堆石子合并成一堆石子合并成一堆石子的合并方式
    • 属性：MIn，所有合并方式的代价的最小值，f[1,n]就是所求答案
  • 状态计算：
    • 将第i堆到第j堆石子合并成一堆石子合并成一堆，最后一步一定是将两堆合并为一堆，那我们可以以最后一次合并的“分界线”的位置来分类：对于区间$[i,j]$，可以分为左边一堆为$[i,k]$，右边一堆为$[k+1,j]$ 。
    • 计算这种合并方式的代价可以用左边一堆的代价f[i,k]，加上右边一堆的代价f[k+1,j]，再加上合并左右两堆需要的代价，即区间[i,j]内元素的代价和。而求某一个区间内的元素和可以用之前学过的前缀和来计算（秒啊）
    • 则状态转移方程为：$f[i,j=\min (f[i,k]+f[k+1,j]+S[j]-S[i-1])$，$k=i\sim j-1$，时间复杂度为$O(n^2 \cdot n)=O(n^3)$（状态数量为$n^2$，每次状态计算量，需要枚举$k$，为$n$）

写区间DP的代码要留意下循环的写法，要保证算每个f[i][j]时用到的状态都已经是计算好的，因此要留意下枚举的顺序，这题我们可以枚举区间长度（这里指的是区间中元素的个数，并不是数学上区间的长度），从小到大，从2开始即可，因为$len=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
27
28
29
30
31
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 310;

int n;
int s[N];     //表示前缀和
int f[N][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];
    
    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;    //求最小值，千万要记得将状态初始化为INF
            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]);
        }
    
    printf("%d\n", f[1][n]);
    
    return 0;
}

力扣DP问题汇总