最短编辑距离

 活动 - AcWing

1)删除 *** 作：把a[i]删掉之后a[1~i]和b[1~j]匹配
            所以之前要先做到a[1~(i-1)]和b[1~j]匹配
            f[i-1][j] + 1
2)插入 *** 作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j]
            那填之前a[1~i]和b[1~(j-1)]匹配
            f[i][j-1] + 1
3)替换 *** 作：把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配
            那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配
            f[i-1][j-1] + 1
            但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即
            f[i-1][j-1] + 0

初始状态：

  f[0][i]如果a初始长度就是0，那么只能用插入 *** 作让它变成b
  f[i][0]同样地，如果b的长度是0，那么a只能用删除 *** 作让它变成b

#include 
using namespace std;

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

int main()
{
    int n,m;
    
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>b[i];
        
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j] = 0x3f3f3f3f;//求最小值把dp初始成无穷大
        }
    }
    
    for(int i=0;i<=n;i++)
    {
        dp[i][0] = i;//b数组长度为0，a数组删i次
    }
    
    for(int i=1;i<=m;i++)
    {
         dp[0][i] = i;//a数组长度为0，b数组增加i次
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + 1;//删除或增加
            if(a[i] == b[j]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);//相等不替换
            else dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);//不相等替换
        }
    }
    
    cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5503464.html