ACM 动态规划编辑距离

野性酷女 2022-07-12 09:52 296阅读 0赞

很久没有更博了..刚开学忙得飞起0..0

最近刷题发现自己有意逃避算法题，很生气啊自己居然潜意识逃避了...

所以今天很认真的写个动态规划！

虽然这是最简单的动态规划...

**TOJ 1072：编辑距离**

描述

假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。  
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。  
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。  
例如：a="ABC",b="CBCD",则a与b的编辑距离为2。  
你的任务就是：编一个快速的程序来计算任意两个字符串的编辑距离。

输入

输入包含多组测试数据。每组测试数据一行，为字符串A和字符串B。  
字符串的长度不大于1024，且全为字母。

输出

编辑距离。

样例输入

ABC CBCD

样例输出

定义一个二维数组p\[i\]\[j\]表示前 字符串s 前i个字符与t 字符串前j个字符的距离。

1）初始条件

dp\[i\]\[0\]=i;

dp\[0\]\[j\]=j;

2)规律

if(s\[i\]==t\[j\])

cost=0;

else cost=1;

dp\[i\]\[j\]=min\{dp\[i\]\[j-1\]+1,dp\[i-1\]\[j\]+1,dp\[i-1\]\[j-1\]+t\};

其中:dp\[i\]\[j-1\]+1 表示删除;

dp\[i-1\]\[j\]+1 表示插入;

dp\[i-1\]\[j-1\]+t 表示修改。

分享一个很好的解析：http://taop.marchtea.com/05.02.html

#include <iostream>  
    using namespace std;  
    #define min(A,B) ((A)<(B)?(A):(B))  
    int dp[2000][2000];  
    int EditDistance(char *s,char *t)  
    {  
       int i,j,cost;  
       int slength=strlen(s);  
       int tlength=strlen(t);  
       dp[0][0]=0;  
       for(i=1;i<=slength;i++)  
       dp[i][0]=i;  
       for(j=1;j<=tlength;j++)  
       dp[0][j]=j;  
       for(i=1;i<=slength;i++)  
       {  
           for(j=1;j<=tlength;j++)  
           {  
               if(s[i-1]==t[j-1])  
               cost=0;  
               else  
               cost=1;  
               dp[i][j] = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+cost);  
           }  
       }  
          return dp[slength][tlength];  
    }  
    int main()  
    {  
        char s[1025],t[1025];  
         while(cin>>s>>t)  
         {  
             int minx;  
             minx=EditDistance(s,t);  
             cout<<minx<<endl;  
         }  
     return 0;  
    }