贴一波地址 https://www.acwing.com/problem/content/904/
总结：
1.别纠结于怎么变换到b串，只需要知道多少步即可
2.注意初始化
3.注意初始化后，不能改变初始化的值
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; int n, m; char a[1005], b[1005]; int dp[1005][1005]; int main() { scanf("%d%s",&n, a+1); scanf("%d%s",&m, b+1); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) dp[i][j] = inf; for(int i = 1; i <= n; i++) dp[i][0] = i; for(int i = 1; i <= m; i++) dp[0][i] = i; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1); if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i-1][j-1]); else dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1); } printf("%d\n",dp[n][m]); return 0; }