（2014-2）計算兩個字元串的編輯距離

問題描述：

把兩個字元串變成相同的三個基本操作定義如下：

1.  修改一個字元（如把a  變成b）

2.  增加一個字元(如abed  變成abedd)

3.  删除一個字元（如jackbllog  變成jackblog）

針對于jackbllog 到jackblog  隻需要删除一個或增加一個l  就可以把兩個字元串變為相同。把這種操作需要的最小次數定義為兩個字元串的編輯距離L。編寫程式計算指定檔案中字元串的距離。輸入兩個長度不超過512 位元組的ASCII 字元串，在螢幕上輸出字元串的編輯距離。

輸入樣例：

輸入：

Hello world!
Hello word!
           

輸出：

1
           

思路：

DP問題：具體思路 兩個字元串的編輯距離-動态規劃方法

用 dp[i][j] 表示到str1的第i個字元與str2的第j個字元的編輯距離，可以得到如下的動态規劃方程：

   其中， 

首先我們令word1和word2分别為：michaelab和michaelxy

1. dis[0][0]表示word1和word2都為空的時候，此時他們的Edit Distance為0。 
2. dis[0][j]就是word1為空，word2長度為j的情況，此時他們的Edit Distance為j，也就是從空，添加j個字元轉換成word2的最小Edit Distance為j
3. 同理dis[i][0]就是，word1長度為i，word2為空時，word1需要删除i個字元才能轉換成空，是以轉換成word2的最小Edit Distance為i

4. 對于上面例子最後一位：如果b==y, 那麼：dis[i][j] = dis[i-1][j-1]。                                                              

       如果b!=y，那麼：添加：也就是在michaelab後面添加一個y，那麼word1就變成了michaelaby，此時  dis[i][j] = 1 + dis[i][j-1]；删除：也就是将michaelab後面的b删除，那麼word1就變成了michaela，此時dis[i][j] = 1 + dis[i-1][j]；替換：也就是将michaelab後面的b替換成y，那麼word1就變成了michaelay，此時dis[i][j] = 1 + dis[i-1][j-1]；

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 10010;
int dp[N][N];

int calculateStrDistance(string sA, string sB)
{
	int lA = sA.length(), lB = sB.length();
	//邊界
	for (int i = 0; i <= lA; ++i)
	{
		dp[i][0] = i;
	}
	for (int j = 0; j <= lB; ++j)
	{
		dp[0][j] = j;
	}

	/*求中間的編輯距離值*/
	for (int i = 1; i <= lA; ++i)
	{
		for (int j = 1; j <= lB; ++j)
		{
			int flag = 0;
            //字元串從0開始存儲
			if (sA[i - 1] != sB[j - 1])
			{
				flag = 1;
			}
            //狀态轉移方程
			dp[i][j] = min(dp[i - 1][j - 1] + flag, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
		}
	}
	return dp[lA][lB];
}


int main()
{
    string sA, sB;
    getline(cin, sA);
    getline(cin, sB);
	cout << calculateStrDistance(sA, sB) << endl;
	return 0;
}