线性DP

本讲前言

我们把具有线性“阶段”划分的动态规划算法统称为线性DP。

本讲我们将学习数字三角形、最长上升子序列（LIS），最长上升子序列二分优化、最长公共子序列、以及一题习题：最短编辑距离 、编辑距离，共六题。

同样的，在学习本讲例题、习题中，我们继续贯彻以集合为核心的分析法去分析每一道题。

经典例题

例题 数字三角形

问题描述

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

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

输入格式

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

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

数据范围：$1 \le n \le 500$, $-10000 \le 三角形中的整数 \le 10000$

输出格式

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

输入样例

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

输出样例

30

题目分析

思路一：

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 550;
int a[N][N], f[N][N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> a[i][j];
    memset(f, -0x3f, sizeof f);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            if(i == 1 && j == 1) f[i][j] = a[i][j];
            else
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
    int ans = -1e9;
    for(int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
    cout << ans;
    return 0;
}

思路二：

#include <iostream>
using namespace std;
const int N = 510;
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 - 1;i >= 1;i--) {
        for (int j = 1;j <= i;j++) {
            f[i][j] = max (f[i + 1][j],f[i + 1][j + 1]) + a[i][j];
        }
    }
    cout << f[1][1] << endl;
    return 0;
}

通过本题可以发现，状态表示方法、含义、条件不同，最后状态转移（集合划分）的计算也会不同，关键是在于我们在处理过程中保证能够得到每一步的答案，且这个答案一定不漏掉任何正确的答案。

其实，DP本身也是对暴力枚举的优化，利用了已知信息去推理！

例题 最长上升子序列I（LIS）

题目描述

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

输入格式

第一行包含整数 $N$。

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

数据范围：$1 \le N \le 1000$，$-10^9 \le 数列中的数 \le 10^9$

输出格式

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

输入样例

7
3 1 2 1 8 5 6

输出样例

4

题目分析

示例代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int main() {
    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[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    int mx = 1;
    for(int i = 1; i <= n; i++)
        mx = max(mx, f[i]);
    cout << mx;
    return 0;
}

例题 最长上升子序列II

题目描述

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

输入格式

第一行包含整数 $N$。

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

数据范围：$1 \le N \le 100000$，$-10^9 \le 数列中的数 \le 10^9$

输出格式

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

输入样例

7
3 1 2 1 8 5 6

输出样例

4

题目分析

本题与上题的区别在于，数据范围扩大了，此时如果还使用例题二的做法（$O(n^2)$），就会超时，那么我们先来分析下，有没有什么地方可以进一步优化，也就是哪些重复的部分可以省去。

先来思考一个例子：5 3 ...

此例子开头是 $5$ 和 $3$，对于这个例子，此时长度均为 $1$，但是在后续求最长上升子序列的过程中，我们永远不可能用到数字 $5$ 了，思考下为什么？

搞清楚这个例子，我们就可以想到，如果当前的子序列是最优子序列（每一个都是最优的值），那么我们只需要往后面添加值或更新已经求过的最小值就好了，有一个比较可行的方法是：用 $f_i$ 来记录长度为 $i$ 的子序列末尾的最小值。

假设，我们现在已经求出了$f_1,f_2,f_3$， 也就是长度为 $1,2,3$ 的最小值，现在枚举到了$a_i$，我们该如何将 $a_i$ 更新状态呢，分为两种情况：

第一种情况，$a_i$ 比 $f_3$ 要大，此时直接得到 $f_4=a_i$，因为前面都会比它小。 第二种情况，$a_i$ 比 $f_3$ 小或者相等，我们则用 $a_i$ 去更新 $f_1, f_2$ 的值，比如：如果 $a_i$ 大于 $f_1$ 但是小于 $f_2$，那么说明 $a_i$ 可以更新长度为 $2$ 的子序列，即 $f_2 = a_i$ ，这样又能保证 $f_2$ 的最优性。

实际上，这个做法就是，在每一个新来的$a_i$，看它能更新哪个$f_j$的值，因为我们$f$数组一定是递增的（可以证明）。 而在递增序列中找到最后一个小于$a_i$的位置，用二分查找即可。

时间复杂度分析：状态数$O(n)$ * 转移次数$O(logn)$ $= O(nlogn)$

示例代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 20;
int a[N], f[N];

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

    for(int i = 1; i <= n; i++) cin >> a[i];
    
    int len = 0;
    f[0] = -2e9;
    for(int i = 1; i <= n; i++) {
        int l = 0, r = len;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(f[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        
        len = max(len, r + 1);
        f[r + 1] = a[i];
    }
    cout << len;
    
    return 0;
}

使用lower_bound()代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 20;
int a[N], f[N];

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

    for(int i = 1; i <= n; i++) cin >> a[i];
    
    int len = 0;
    f[0] = -2e9;
    for(int i = 1; i <= n; i++) {
        if(a[i] > f[len])
            f[++len] = a[i];
        else
            *lower_bound(f, f + len + 1 , a[i])  = a[i];
        
    }
    cout << len;
    
    return 0;
}

例题 最长公共子序列

题目描述

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

输入格式

第一行包含两个整数 $N$ 和 $M$。

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

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

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

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

输出格式

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

输入样例

4 5
acbd
abedc

输出样例

3

题目分析

上图值得注意的是：状态计算中集合划分的第一部分其实是被包含在第二部分或者第三部分中的，所以实际代码中可以不写，其次，对于第二个部分和第三部分，所写状态其实不是完全精准的，以第二个部分举例说明：

不选 $a_i$，选 $b_i$，但是 $f[i-1][j]$ 是可以确保不选 $a_i$，但是不能确保一定选 $b_j$，但是为什么这样求也是对的呢？

那是因为我们求的是最大值，而 $f[i-1][j]$ 是包含了选择 $b_j$ 部分的，对于没有选择 $b_j$ 部分是不影响我们结果的，只要集合能被覆盖即可。

类似于：求 $A,B,C$ 的最大值，其实是可以先求 $a = max(A,B)$ 再求 $b = max(B,C)$，最后再求一次 $max(a,b)$ 即可。

示例代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1111;
int f[N][N];
int main()
{
    int n, m;
    string a, b;
    cin >> n >> m >> a >> b;
    a = " " + a;
    b = " " + b;
    
    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;
}

习题一 最短编辑距离

问题描述

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

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

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

输入格式

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

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

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

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

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

数据范围：$1 \le n, m \le 1000$

输出格式

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

输入样例

10
AGTCTGACGC
11
AGTAAGTAGGC

输出样例

4

题目分析

对于状态计算：

• 删除$a_i$，意味着需要让$f_{i-1,j}$的值加$1$，因为删除之后可以让$a_1...a_{i-1}$等于$b_1...b_j$
• 在$a_i$处增加一个字符，意味着需要让$f_{i,j-1}$的值加$1$，因为增加之后可以让增加字符等于$b_j$，那么实现$a$的$1...i$个字符变成b的$1...j$字符。
• 修改$a_i$：看目前$a_i$是否等于$b_j$，如果相等，则没必要改，状态为$f_{i-1,j-1}$，如果不相等，则需要改，状态为$f_{i-1,j-1} + 1$

示例代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N][N];


int main() {
    int n, m;
    string a, b;
    cin >> n >> a >> m >> b;
    a = " " + a;
    b = " " + b;
    
    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] + 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];
    
    return 0;
}

习题二 编辑距离

问题描述

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

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

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

输入格式

第一行包含两个整数 $n$ 和 $m$。

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

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

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

数据范围：$1 \le n, m \le 1000$

输出格式

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

输入样例

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例

1
3

题目分析

直接用习题一的方法即可。

示例代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N];
int find(string a, string b) {
    int n = a.size(), m = b.size();
    a = " " + a;
    b = " " + b;
    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] + 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); //改
        }
    return f[n][m];
}

int main() {
    int n, m;
    string a[N], b;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    while (m -- ) {
        int k;
        cin >> b >> k;
        int sum = 0;
        for(int i = 1; i <= n; i++) {
            int ans = find(a[i], b);
            if(ans <= k) sum ++;
        }
        cout << sum << endl;
    }
    
    return 0;
}