当前位置：首页 > news >正文

Acwing 线性DP

news 2025/4/30 15:25:30

状态转移方程呈现出一种线性的递推形式的DP，我们将其称为线性DP。

Acwing 898.数字三角形

在这里插入图片描述
实现思路：

对这个三角形的数字进行编号，状态表示依然可以用二维表示，即f(i,j),i表示横坐标（横线），j表示纵坐标（斜线）
用f(i,j)表示到点(i,j)的路径最大数字之和。对集合进行划分，到达某点(i,j)只可能经过左上方的点(i-1,j-1)或右上方的点(i-1,j)。用a[i][j]表示当前点的数值；
故可得状态转移方程：f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])

具体实现代码（详解版）：

#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];  }}// 初始化 DP 数组，将所有 f[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];// 状态转移方程：f[i][j] 表示到达第 i 行第 j 列的最大路径和for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {// 到达 f[i][j] 位置有两种可能：// 1. 来自 f[i-1][j-1]，即从左上角过来// 2. 来自 f[i-1][j]，即从正上方过来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;
}

这道题还可以从下往上递推，考虑f[i][j]来自左下方和来自右下方两种情况，这样就不需要处理边界问题，而且最后的结果一定集中在f[1][1]中。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 510, INF = 1e9;  // 定义常量 N 为最大行数，INF 为极大值
int n;  // 表示三角形的行数
int f[N][N], a[N][N];  // f 用于存储从底部到达每个位置的最大路径和，a 存储三角形中的数字int main() {int n;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] 表示在 (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;
}

Acwing 895.最长上升子序列

在这里插入图片描述
实现思路：

一维数组f[i]表示以第i个数为结尾的最长递增子序列的长度；
状态划分：选定i为结尾的递增子序列，则再从[0,i-1]中筛选出倒数第二个位置的数，使递增子序列的长度最大。注意这个倒数第二个位置的数必须满足a[j]<a[i]，这样才能保证递增序列；
状态转移方程为f[i]=max(f[i],f[j]+1);

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010; int n; 
int a[N], f[N];  // a 存储输入的数组, f 存储以每个元素结尾的最长上升子序列的长度int main(){cin >> n;  for(int i = 1 ; i <= n ; i ++) cin >> a[i];  // 动态规划计算最长上升子序列for(int i = 1 ; i <= n ; i ++) {f[i] = 1;  // 初始状态，每个元素自身可以作为一个长度为1的子序列for(int j = 1 ; j < i ; j ++){// 如果前面的元素 a[j] 比当前元素 a[i] 小，则可以考虑将 a[i] 接在 a[j] //之后形成一个更长的子序列if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);  // 更新 f[i]，选择使 f[i] 最大的方案}}// 找到 f 数组中的最大值，即最长上升子序列的长度int res = 0;for(int i = 1 ; i <= n ; i ++) res = max(res, f[i]);cout << res << endl;  return 0;
}

那有没有办法进行优化呢？最长上升子序列（LIS）问题的时间复杂度为 $O(n^2),$ 我们可以通过贪心算法 + 二分查找来将时间复杂度优化为 $O (n l o g n)$ .

Acwing 896. 最长上升子序列 II

在这里插入图片描述
实现思路：

首先在上述解法的基础上，假如存在一个序列3 1 2 5，以3结尾的上升子序列长度为1，以1为结尾的上升子序列长度也为1，这是两个长度一样的上升子序列（伏笔：结尾元素1<3）。在继续向后遍历查找时，看3这个序列，当出现一个比3大的数时，以3结尾的上升子序列就会更新，比如遍历到5了，那么上升序列变为3 5；同时注意到这个5一定会加入到以1结尾的上升序列中（因为1<3，那么1<5的），那么含有1的上升序列长度一定是>=2的，因为中间可能存在<3但>1的数（比如这里就有2，序列长度就更新为3）。可以看出存在3的这个序列就不需要枚举了，因为存在1的序列往后遍历的长度是一定大于你这个存在3的序列的（前提是以1结尾和以3结尾的上升序列长度相等），那我找最长的时候怎么都轮不到包含3的序列头上，那我一开始在1和3结尾的序列之后直接舍弃枚举包含3的序列了（去掉冗余）。
在以上的分析得到：当存在两个上升序列长度相同时，结尾数更大的序列可以舍去不再枚举，所以每次就干脆选出相同长度结尾元素最小的序列继续操作
那么状态表示更改为：f[i]表示长度为i+1(因为下标从0开始)的最长上升子序列，末尾最小的数字。(所有长度为i+1的最长上升子序列所有结尾中，结尾最小的数) 即长度为i的子序列末尾最小元素是什么。
状态计算：序列长度+1(cnt++)，当前末尾最小元素变为a[i]。 **若a[i]小于等于f[cnt-1],**说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于(不能直接写大于，要保证单增) a[i]的数的位置mid，将这个数a[i]放在mid的位置（其实就是找到a[i]适合存在的位置，不改变序列长度）。

具体实现代码（版本一）：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int N = 100010;  // 定义最大数组大小
int n, cnt;
int a[N], f[N];int main() {// 输入数组长度cin >> n;// 输入数组元素for (int i = 0; i < n; i++) {cin >> a[i];}// 初始化 cntcnt = 0;// 处理第一个元素f[cnt++] = a[0];for (int i = 1; i < n; i++) { // 注意这里应为 i < nif (a[i] > f[cnt - 1]) {f[cnt++] = a[i]; // 如果 a[i] 大于当前上升序列末尾的数，则末尾加入} else {// 使用二分查找int l = 0, r = cnt - 1;while (l < r) {int mid = (l + r) / 2;if (f[mid] >= a[i]) r = mid; // 找到第一个 >= a[i] 的位置else l = mid + 1;}f[r] = a[i]; // 替换找到的位置}}cout << cnt << endl; // 输出最长上升子序列的长度return 0;
}

版本二（使用lower_bound函数，找到第一个 >= a[i] 的位置）

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int N = 100010;  // 定义最大数组大小
int n;
int a[N];int main() {// 输入数组长度cin >> n;// 输入数组元素for (int i = 0; i < n; i++) {cin >> a[i];}// 用于维护当前的上升子序列vector<int> d;// 遍历数组的每个元素for (int i = 0; i < n; i++) {// 使用二分查找找到第一个 >= a[i] 的位置auto it = lower_bound(d.begin(), d.end(), a[i]);if (it == d.end()) {// 如果没有找到比 a[i] 大的元素，则将 a[i] 添加到序列末尾d.push_back(a[i]);} else {// 否则，用 a[i] 替换掉找到的这个位置的元素*it = a[i];}}// 最终 d 的大小就是最长上升子序列的长度cout << d.size() << endl;return 0;
}

Acwing 897. 最长公共子序列

在这里插入图片描述
实现思路：

f(i,j)表示第一个序列的前i个字母中出现并且在第二序列前j个字母中出现的最长的公共子序列长度
状态可划分为4种情况：a[i]表示为第一个序列中第i个字符，b[j]表示第二个子序列中第j个字符
- 00：表示最长公共子序列中一定不包含字符a[i]和b[j]，用f[i-1][j-1]表示
- 01：表示最长公共子序列中一定不包含字符a[i]，一定包含b[j]。不能用f[i-1][j]表示（不是等价的），因为f[i-1][j]表示的是该公共子序列一定不包含a[i]，但b[j]不一定，可能包含也可能不包含。故f[i-1][j]是包含01这种情况的。但是由于求的是最大子序列的长度（而不是具体元素），所以求解的时候可以用f[i-2][j]来求解
- 10：表示最长公共子序列中一定包含字符a[i]，一定不包含b[j]。用f[i][j-1]求解，但含义不等价，同上。
- 11：表示最长公共子序列中一定包含字符a[i]和b[j]，用f[i-1][j-1]+1表示，但注意需要满足a[i] = b[j]才行，因为公共子序列，既然包含a[i]、b[i]，那么两者必然相等才行
00的情况实质上已经被包含在01、10两种情况之中，所以可以省略，故只需求下面三种状态

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;char a[N], b[N];
int f[N][N];
int n, m;int main() {cin >> n >> m;// 输入字符串，保留 a[0] 和 b[0] 为空字符cin >> (a + 1) >> (b + 1);// 动态规划计算最长公共子序列for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 如果字符相同，则长度加 1if (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;return 0;
}

Acwing 902.最短编辑距离

在这里插入图片描述
实现思路：

f(i,j)表示，集合为所有将第一个字符串前i个字符变为第二个字符串前j个字符的方式的最少操作数量
集合划分：以第一个字符串i处可能进行的三种不同操作后转化为第二个字符串。
- 删去第i个字符，即前i-1个字符已经与第二个字符串的前j个字符相同，因此只需要在上一个状态加上删去操作即可，即f(i,j)=f(i-1,j)+1；
- 增加第i个字符才能与第二个字符串的前j个字符相等，即前i-1个字符已经与第二个字符串的前j-1个字符相同，因此只需要在上一个状态加上增加第i个字符操作即可，即f(i,j)=f(i-1,j-1)+1；
- 修改第i个字符，即前i-1个字符已经与第二个字符串的前j-1个字符相同，再比较第i个字符是否与第j个字符相同，若相同就不用操作，若不同则需要增加一次修改操作,即f(i,j)=f(i-1,j-1)+0 or 1。
最终f(i,j)取三者最小值

#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() {cin >> n >> (a + 1) >> m >> (b + 1);// 初始化边界条件for (int i = 0; i <= m; i++) f[0][i] = i; // 如果 a 为空，编辑距离就是 b 的长度for (int i = 0; i <= n; i++) f[i][0] = i; // 如果 b 为空，编辑距离就是 a 的长度// 动态规划求解最小编辑距离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] + 1);else // 字符相等时，不需要操作，保持之前的值f[i][j] = min(f[i][j], f[i - 1][j - 1]);}}cout << f[n][m] << endl;return 0;
}

Acwing 899.编辑距离

在这里插入图片描述

实现思路：与上题思路一致，不过在读入时有所区别，该题需要读入n个字符串，m次问询，因此读入n个第一个字符串，然后在每次问询中读入第二个字符串，计算n个第一个字符串要变化到第二个字符串的次数，统计在规定次数内的第一个字符串有几个。

具体实现代码（详解版):

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 15, M = 1010; // 定义常量 N 表示字符串最大长度，M 表示字符串的最大数量
int n, m;
int f[N][N]; // DP 数组，用于存储编辑距离的中间结果
char str[M][N]; // 存储多个输入字符串，每个字符串最大长度为 N// 求两个字符串的编辑距离
int edit_dis(char a[], char b[]) {// 获取两个字符串的长度int la = strlen(a + 1), lb = strlen(b + 1);// 初始化DP数组，表示空串与某一字符串之间的编辑距离for (int i = 0; i <= lb; i++) f[0][i] = i; // 第一行：空串变成b的前i个字符需要插入i次for (int i = 0; i <= la; i++) f[i][0] = i; // 第一列：a的前i个字符变成空串需要删除i次// 计算编辑距离for (int i = 1; i <= la; i++) { // 遍历字符串a的每个字符for (int j = 1; j <= lb; j++) { // 遍历字符串b的每个字符// 增或删操作，取最小值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] + 1); // 替换操作} else {f[i][j] = min(f[i][j], f[i - 1][j - 1]); // 如果字符相同，不需要操作}}}return f[la][lb]; 
}int main() {cin >> n >> m; for (int i = 0; i < n; i++) cin >> (str[i] + 1); // 输入 n 个字符串，str[i] 表示第 i 个字符串// 处理每个查询while (m--) {char s[N]; // 用于存储每次查询的字符串int limit, res = 0; // limit 表示编辑距离的限制，res 用于记录满足条件的字符串数量cin >> (s + 1) >> limit; // 输入查询字符串 s 和编辑距离限制 limit// 遍历每个输入的字符串，计算其与查询字符串的编辑距离for (int i = 0; i < n; i++) {// 如果编辑距离小于等于给定的限制，则结果加1if (edit_dis(str[i], s) <= limit) res++;}cout << res << endl;}return 0;
}