51nod 1183 编辑距离问题

2个字符串，把s1转换到s2最少操作，并且把这个操作过程输出。

操作包括3种：删除一个字符，增加一个字符，改变一个字符，操作仅对s1执行，使其等于s2.

分析这个题很想最大公共子序列问题
对于两个字符串，如果 a[i]=b[j] 则不必进行操作
如果a[i]!=b[j] 那么有三种情况， 删除 ，增加 改变 dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[1010],b[1010];
int dp[1010][1010];
int main()
{
    cin>>a>>b;
    int n=strlen(a);
    int m=strlen(b);
    for(int i=0;i<=n;i++) dp[i][0]=i;
    for(int j=0;j<=m;j++) dp[0][j]=j;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1];
            }
            else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}