需要改动的次数为,目标字符串长度 - 两字符串最大公共子序列的长度
#include<iostream> #include<cstring> using namespace std; const int N=1010; int n,m; char a[N],b[N]; int f[N][N]; //f[i][j]表示a中前i个字符和b的前j个字符的公共子序列长度的最大值 int main() { cin>>a+1>>b+1; n = strlen(a+1); m = strlen(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]); //最后一个字符不相同的时候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); //最后一个字符相同再更新f[i][j]最值 } cout<<n - f[n][m]; //步数为原长-最大公共子序列的长度 return 0; }
0.0分
0 人评分