线性DP
数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
状态表示
f[i][j] : 所有从起点走到(i,j)的路径最大值
状态计算
f[i][j] = Max(f[i-1][j-1],f[i-1][j]) + a[i][j]
最长上升子序列（LIS）
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。
朴素算法
状态表示
f[i]:所有以第i个数结尾的上升子序列
状态计算
const int N = 1010; int f[N][N]; char a[N],b[N]; int main() { int n,m;cin >> n >> m; scanf("%s%s",a+1,b+1); 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]; return 0; }
最短编辑距离
给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。
状态表示
f[i][j]：所有将a[1～i]变成b[1～j]的操作方式
状态计算
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 1010; char a[N], b[N]; int n, m; int f[N][N]; int main() { scanf("%d%s", &n, a + 1); scanf("%d%s", &m, b + 1); 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个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
进行多次最短编辑距离比较即可
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 15, M = 1010; char s[M][N]; int f[N][N]; int n, m; int edit_distance(char a[], char b[]) { int la = strlen(a + 1); int lb = strlen(b + 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); f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j])); } } return f[la][lb]; } int main() { cin >> n >> m; for (int i = 0;i < n;++i)scanf("%s", s[i] + 1); while (m--) { int limit; char str[N]; scanf("%s%d", str + 1, &limit); int res = 0; for (int i = 0;i < n;++i) { if (edit_distance(str, s[i]) <= limit) ++res; } cout << res << endl; } return 0; }
