AcWing 902. 最短编辑距离
视频讲解：
【E07 线性DP 编辑距离】
两套代码的字符串存储数组都是从1开始存储的！！！！
硬套公式：
#include<iostream>
#include<algorithm>
const int N = 1010;
using namespace std;
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;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] , 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 - 1][j - 1] + 1,f[i][j]) ;if(a[i]==b[j]) f[i][j] = f[i-1][j-1];else{f[i][j] = min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;}}}cout << f[n][m];return 0;
}
标准答案
#include<iostream>
#include<algorithm>
const int N = 1010;
using namespace std;
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;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] , 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 - 1][j - 1] + 1,f[i][j]) ;}}cout << f[n][m];return 0;
}