DP optimization algorithm
time complexity O(n^2) room complexity O(n)
dp[i][j]:a的前i个字符和b的前j个字符的最短编辑距离
1.a[i]==b[j]则若以a[i]和b[j]结尾,则相当于不操作,最短编辑距离为dp[i-1][j-1]
2.a[i]!=b[j]则为(dp[i-1][j]+1:减去a[i];dp[i][j-1]+1:减去b[j];dp[i-1][j-1]+1:替换a[i]或者b[j]使两者相等)三类操作的最小编辑次数
由上图可知,dp[i][j]依赖于dp[i-1][j]、dp[i-1][j]、dp[i-1][j-1]。
只依赖于两行dp数据,故可以进行dp大小优化,为dp[2][j]
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
const int N = 1009;
char a[N], b[N];
int dp[2][N];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin>>n>>a+1>>m>>b+1;
//初始化
for(int i = 0; i <= m; i++) dp[0][i] = i;
for(int i = 1; i <= n; i++){
//两行dp循环使用
int now = (i & 1), old = (i - 1 & 1);
dp[now][0] = i;//初始化
for(int j = 1; j <= m; j++){
if(a[i] == b[j]) dp[now][j] = dp[old][j-1];
else dp[now][j] = min(min(dp[old][j], dp[now][j-1]), dp[old][j-1]) + 1;
}
}
cout<<dp[n & 1][m];
return 0;
}