信息学奥赛一本通1276：【例9.20】编辑距离

题目：
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。



#include <bits/stdc++.h>
using namespace std;
/*
思路：
f[i][j]表示A的前i个字符变成B的前j个字符所需要的最少操作数
对于最后一步操作A[i]可以分四种情况：
1)删除A[i]    f[i-1][j]+1 表示A的前i-1个字符就可以变成B了，A[i]是多余的，删掉
2)添加B[j]    f[i][j-1]+1 表示A的前i个字符可以变成B的前j-1，但A长度不够，需要添加B[j]来变成B
3)替换A[i]为B[j]  f[i-1][j-1]+1  表示A的前i-1字符变成B的前j-1后,A[i]与B[j]不同，需要把A[i]替换成B[j]来变成B
4)不变        f[i-1][j-1]        A[i]==B[j]
对上述情况取最小值得到结果
*/

int A[2010],B[2010];
int f[2010][2010];
string a,b;
int main(){
    cin>>a>>b;
    int lenA=a.length();
    int lenB=b.length();
    for(int i=1;i<=lenA;i++){
        A[i]=a[i-1];
    }
    for(int i=1;i<=lenB;i++){
        B[i]=b[i-1];
    }
    //**********一个为空，则步数为另一个的长度
    for(int i=1;i<=lenA;i++)
            f[i][0]=i;
    for(int i=1;i<=lenB;i++)
            f[0][i]=i;
    
    
    
    for(int i=1;i<=lenA;i++)
      for(int j=1;j<=lenB;j++){
          int flag=0;
          if(A[i]!=B[j])
              flag=1;
          f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+flag);
      }
      
      cout<<f[lenA][lenB];
        
    return 0;
    
    
}