线性DP
数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
状态表示
f [ i ] [ j ] f[i][j] f[i][j] : 所有从起点走到 ( i , j ) (i,j) (i,j)的路径最大值
状态计算
f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j − 1 ] , f [ i − 1 ] [ j ] ) + a [ i ] [ j ] f[i][j] = Max(f[i-1][j-1],f[i-1][j]) + a[i][j] f[i][j]=Max(f[i−1][j−1],f[i−1][j])+a[i][j]
最长上升子序列（LIS）
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。
朴素算法
状态表示
f [ i ] f[i] f[i]:所有以第i个数结尾的上升子序列
状态计算
$f[i] = Max(f[i],f[j] +1),,,,,(j <= i-1 $ & & a [ j ] < a [ i ] ) \&\& a[j] < a[i]) &&a[j]<a[i])
时间复杂度 O （ N 2 ） O（N^{2}） O（N2）
int f[N], a[N];
int main() {
int n;cin >> n;
for (int i = 1;i <= n;++i)cin >> a[i];
for (int i = 1;i <= n;++i) {
f[i] = 1;
for (int j = 1;j <= i;++j) {
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
}
int res = -INF;
for (int i = 1;i <= n;++i)
res = max(f[i], res);
cout << res << endl;
return 0;
}
二分查找优化
#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 = 100010;
int n;
int a[N], q[N];
int main() {
cin >> n;
for (int i = 0;i < n;++i)scanf("%d", &a[i]);
int len;
q[0] = -2e9;
len = 0;
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);
q[r + 1] = a[i];
}
cout << len << endl;
return 0;
}
最长公共子序列（LCS）
给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。
状态表示
f [ i ] [ j ] f[i][j] f[i][j] 所有在第一个序列的前 i i i个字母中出现，且在第二个序列的前 j j j个字母中出现的子序列
状态计算
f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j − 1 ] , f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] , f [ i − 1 ] [ j − 1 ] + 1 ) f[i][j] = Max(f[i-1][j-1],f[i-1][j],f[i][j - 1],f[i-1][j-1] + 1) f[i][j]=Max(f[i−1][j−1],f[i−1][j],f[i][j−1],f[i−1][j−1]+1)
实际上 f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i−1][j−1]已经包含在 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]和 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]里面 因为求的是最大值 所以没必要重复计算
所以 a [ i ] = = b [ j ] a[i] == b[j] a[i]==b[j]时 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 f[i][j] = f[i - 1][j-1] + 1 f[i][j]=f[i−1][j−1]+1
a [ i ] ! = b [ j ] a[i] != b[j] a[i]!=b[j]时 f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[i][j] = Max(f[i-1][j],f[i][j-1]) f[i][j]=Max(f[i−1][j],f[i][j−1])
时间复杂度 O ( N ∗ M ) O(N*M) O(N∗M)
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 ] f[i][j] f[i][j]：所有将 a [ 1 ～ i ] a[1～i] a[1～i]变成 b [ 1 ～ j ] b[1～j] b[1～j]的操作方式
状态计算
①增：增加一个字母前 有 a [ 1 , i ] a[1,i] a[1,i]匹配 b [ 1 , j − 1 ] b[1,j-1] b[1,j−1] 即 f [ i ] [ j − 1 ] + 1 f[i][j-1] + 1 f[i][j−1]+1
②删：删除最后一个字母前 有 a [ 1 , i − 1 ] a[1,i-1] a[1,i−1]匹配 b [ 1 , j ] b[1,j] b[1,j] 即 f [ i − 1 ] [ j ] + 1 f[i-1][j] + 1 f[i−1][j]+1
③改：改变最后一个字母后 使得 a [ 1 , i ] a[1,i] a[1,i]匹配 b [ 1 , j ] b[1,j] b[1,j] 如果 a [ i ] = = b [ j ] a[i]==b[j] a[i]==b[j] 无需操作 否则为 f [ i − 1 ] [ j − 1 ] + 1 f[i-1][j-1] + 1 f[i−1][j−1]+1
O ( N 2 ) O(N^{2}) O(N2)
#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;
}
京公网安备 11010502036488号