线性DP
数字三角形
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int n;
int f[N][N], a[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 ++)
f[i][j] = -INF;
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] + 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;
}
最长上升子序列
#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;//设f[i]默认为1,找不到前面数字小于自己的时候就为1
for(int j = 0; 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;
}
最长上升子序列 II
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
int a[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int len = 0;
q[0] = -2e9;
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;
}
最长公共子序列
先尝试用式子 f[i-1,j]
对该类进行计算,但 f[i-1,j]
并不完全等价于这一类,
因为此类所指的是:“a[i]
不包含,而 b[j]
包含”,
而 f[i-1,j]
表示:在 a
串的 1 ~ i-1
中 和 b
串的 1 ~ j
中 选择的最长公共子序列,一定不包含 a[i]
,可能包含 b[j]
也可能不包含,b[j]
的存在情况有两种,简而言之,f[i-1,j]
表示的集合可以分为 两类: “含 b[j]
” 和 “不含 b[j]
” 。
但是我们知道,对于求一个集合的 数量属性 时,我们要保证 “不重不漏”,但是 求最值属性 的时候我们只要保证 “不漏” 即可,“不重” 其实是无所谓的,不影响最终的答案。
因此我们再求第 ③ 类最大值的时候,我们就可以直接用 f[i-1,j]
来覆盖(注意:并不是直接计算出这一类),f[i-1,j]
表示集合完全包含第 ③ 类集合,且一定在 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 >> m >> 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);
}
cout << f[n][m] << endl;
return 0;
}
最短编辑距离
#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有0个字符,只能增加,那么b有几个字符就操作几次
for(int i = 0; i <= n; i ++) f[i][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);
}
cout << f[n][m] << endl;
return 0;
}
编辑距离
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 15, M = 1010;
int n, m;
int f[N][N];
char str[M][N];
int edit_distance(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()
{
cin >> 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_distance(str[i], s) <= limit)
res ++ ;
cout << res << endl;
}
return 0;
}