7-8 编辑距离问题 （30 分) PTA 动态规划

7-8 编辑距离问题 （30 分) 设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。

输入格式: 第一行是字符串A，文件的第二行是字符串B。

提示：字符串长度不超过2000个字符。

输出格式: 输出编辑距离d(A,B)

输入样例: 在这里给出一组输入。例如：

fxpimu xwrs 输出样例: 在这里给出相应的输出。例如：

5

分析： 这道题经分析有三种操作， 1，当字符串有一个不匹配的时候直接删除 2，当少一个字符的时候插入一个字符，但这个可以转化为操作一，所以这个并没有什么卵用。不用考虑。 3，将一个字符该改为另一个字符，用于有两个字符不同，如果我们删除需要两个操纵，但我们使用修改为另一个字符的话，我们的操作只需要一次就好。

那么我们试着用一下动态规划的思想，将原问题划分成与原问题相同的子问题，看看可不可以递推。

加入我们已经直到了a[0]-a[i-1] 这个串和 b[0]-b[j-1] 这个串的距离为x， 那么a[0]-a[i] 和 b[0]-b[j] 这个原问题的解是什么呢？

可知，如果a[i]==b[j]那么dp[i][j] 的答案就是 dp[i-1][j-1] 如果a[i]!=b[j] 那么dp[i][j] 的答案将会是， 删除a[i]: 1+dp[i-1][j], 删除b[j]: 1+dp[i][j] , 修改a[i] 使 a[i]==b[j]: 1+dp[i-1][j-1] 这三个操作中答案最小的那个。

可知可以使用动态规划， 在实际书写代码的时候注意dp数组的初始化。 详见代码：

#include 
using namespace std;
const int maxn=2001;
string a,b;
int dp[maxn][maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    memset(dp,0,sizeof(dp));
    cin>>a>>b;
    a=" "+a;
    b=" "+b;

    for(int i=0;i!=a.size();i++)
    {
        dp[i][0]=i;
    }

    for(int j=0;j!=b.size();j++)
    {
        dp[0][j]=j;
    }

    for(int i=1;i!=a.size();i++)
    {
        for(int j=1;j!=b.size();j++)
        {
            if(a[i]==b[j])
            {
                dp[i][j]=dp[i-1][j-1];
            }
            else
            {
                int t=min(dp[i-1][j],dp[i][j-1])+1;
                t = min(t,dp[i-1][j-1]+1);
                dp[i][j]=t;
            }
        }
    }

//  for(int i=0;i!=a.size();i++)
//  {
//      for(int j=0;j!=b.size();j++)
//      {
//          cout<<dp[i][j]<<" ";
//      }
//      cout<<endl;
//  }

    cout<<dp[a.size()-1][b.size()-1]<<endl;
    return 0;
}