今天看自然语言处理的书籍看到有一个编辑距离的概念，看样子还有点用，就随便写了一下代码。其实这个概念跟做ACM里面的LCS差不多，如果LCS理解透彻的话这个问题几分钟就能敲出来。这是一个DP问题，状态转移方程如下图所示：

 

C++代码：

#include 
     
      #include 
      
       const int maxn = 55;using namespace std;void calc(string t,string s)   //代码很简单，都是按照公式来的，初始化注意一下就OK！{    int lent=t.length(),lens=s.length();    int H[maxn][maxn];    memset(H,0,sizeof(H));        for(int i=0; i
       
        >t>>s;    calc(t,s);    return 0;}
       
      
     

 计算出来的结果就是编辑距离。有什么不对的地方欢迎大家指正！