线性DP
最短编辑距离
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
- 删除–将字符串 A 中的某个字符删除。
- 插入–在字符串 A 的某个位置插入某个字符。
- 替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。
#include<bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(){
scanf("%d%s",&n, a + 1);
scanf("%d%s",&m, b + 1);
for(int i=0;i<=m;i++) f[0][i] = i;
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);
}
printf("%d\n",f[n][m]);
return 0;
}
编辑距离
给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 2e9;
const int N = 15, M = 1010;
int n,m;
char str[M][N];
int f[N][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 - 1][j - 1] + (a[i] != b[j]), f[i][j]);
}
return f[la][lb];
}
int main(){
scanf("%d%d",&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++;
}
printf("%d\n",res);
}
return 0;
}
计数类DP
整数划分
一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。
思路：可以等效为一个完全背包问题，把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形） f[i][j] 表示前i个整数（1,2…,i）恰好拼成j的方案数
求方案数：把集合选0个i，1个i，2个i，…全部加起来
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
因此 f[i][j]=f[i−1][j]+f[i][j−i]; (这一步类似完全背包的推导）
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 1e9+7;
int n;
int f[N];
int main(){
cin >> n;
f[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
f[j] = (f[j] + f[j - i]) % M;
cout << f[n] << endl;
return 0;
}
另一种方法：
集合表示f[i][j]表示总和是i并且恰好能分成j个数的和的方案总数，分类为方案中最小数为1 || 最小值＞1 这两类分别表示为f[i-1][j-1] 和 f[i-j][j]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 1e9+7;
int n;
int f[N][N];
int main(){
cin >> n;
f[0][0] = 1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j] = (f[i-1][j-1] + f[i-j][j]) % M;
int res = 0;
for(int i=1;i<=n;i++) res = (res + f[n][i]) % M;
cout << res << endl;
return 0;
}
