很久沒有更博了..剛開學忙得飛起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

樣例輸出

2

定義一個二維數組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;  }