d p 1 [ i ] [ c ] dp1[i][c] dp1[i][c]表示：在第i个字符为c，且其后面的区间字符完全相同的最小步数。
d p 2 [ i ] [ c ] dp2[i][c] dp2[i][c]表示：将第i个字符变为c，且其后面的区间（不含i）完全相同的最小步数。
转移分情况讨论，具体见代码
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<string> #define SF scanf #define PF printf #define MAXN 1000010 using namespace std; int f1[MAXN][30],f2[MAXN][30]; string s,t; int main(){ cin>>s>>t; int n=s.size(); for(int i=0;i<26;i++){ f1[n-1][i]=(i!=t[n-1]-'a'); f2[n-1][i]=(i!=s[n-1]-'a'); } for(int i=n-2;i>=0;i--) for(int c=0;c<26;c++){ if(t[i]-'a'==c) f1[i][c]=f1[i+1][s[i+1]-'a']; else{ f1[i][c]=f1[i+1][c]+1+(s[i+1]!=t[i]); f1[i][c]=min(f1[i][c],f1[i+1][s[i+1]-'a']+1); f1[i][c]=min(f1[i][c],f2[i+1][t[i]-'a']+1+(c!=t[i+1]-'a')); } if(s[i]-'a'==c) f2[i][c]=f2[i+1][t[i+1]-'a']; else{ f2[i][c]=f1[i+1][s[i]-'a']+1+(s[i+1]-'a'!=c); f2[i][c]=min(f2[i][c],f2[i+1][t[i+1]-'a']+1); f2[i][c]=min(f2[i][c],f2[i+1][c]+1+(s[i]!=t[i+1])); } } PF("%d\n",f1[0][s[0]-'a']); }