描述

这是一个简单的DP问题，（正所谓难者不会会者不难。

状态表示：

f[i,j]：表示a[1~i]更改为b[1~j]所用最短的步数

状态转移：

状态转移分为三种操作：增，删，改，分别对应三种情况。
一，删：
如果删除a[i]使得剩余子串相等，那么说明a[1~i-1]==b[1~j]。
状态转移方程为 f[i-1,j]+1

（为什么删掉的是a[i]？f[i][j]表示a[1~i]和b[1~j]相等时所用最短步数，当进入下一步时，出错的只能是最新进入的字符，所以删除的是最后的字符。增，改同理）

二，增
如果增加a[i]使得相等，那么说明a[1~i]==b[1~j-1]，增加的是b[j]；
状态转移方程为 f[i][j-1]+1
三，改
这里分为三个情况，如果a[i]==b[j]则不用改，不同时，说明至少a[1~i-1]==b[1~j-1]。
状态转移方程为 f[i-1][j-1]+1

关于状态转移方程部分的说明

for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i-1][j]+1,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]);//不同则更改
        }

f[i][j]都是从上一个状态更新而来的，如上文三种的状态。
上一个状态一定已经是最完美状态。

代码

#include<algorithm>
using namespace std;

const int N=1010;
char a[N],b[N];
int f[N][N];

int n,m;
int main(){
    cin>>n;
    cin>>a+1;
    cin>>m;
    cin>>b+1;
    for(int i=0;i<=m;i++) f[0][i]=i;//a 0个字符更新为b i个字符需要增加i次
    for(int i=0;i<=n;i++) f[i][0]=i;//a i个字符更新为b 0个字符需要删除i 次

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i-1][j]+1,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]<<endl;