题目
Problem Description
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1.删除一个字符；
2.插入一个字符；
3.将一个字符改为另一个字符。
对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。
Output
Sample Output
解题思路
定义：
源字符串和目标字符串分别为 source, taregt
状态 dp[i][j] 表示：
source 的前 i 个字符组成的子字符串
与
target 的前 j 个字符组成的子字符串
的编辑距离
操作：
从 source 的第一个字符开始，跟 target 的字符逐个比对；再转移到 source 的下一个字符，跟 target 的字符逐个比对；如此类推，直到 source 的全部字符都比对完。
如果 source 的第 i 个字符和 target 的第 j 个字符相等，那么编辑距离跟状态 dp[i - 1][j - 1] 的编辑距离相等：
dp[i][j] = dp[i - 1][j - 1]；
如果不相等，那么需要看 dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]:
从状态 dp[ i ][j - 1] 到状态 dp[i][j]，从 source 中删除一个字符即可；
从状态 dp[i - 1][ j ] 到状态 dp[i][j]，往 source 中添加一个字符即可；
从状态 dp[i - 1][j - 1] 到状态 dp[i][j]，替换 source 中的一个字符即可。
上面三种操作中选择编辑距离最小的一个。
解题代码
//
// main.cpp
// 字符串的修改
//
// Created by Yeah on 14-7-15.
// Copyright (c) 2014年 Yeah. All rights reserved.
//
#include <iostream>
using namespace std;
int min_of_2(int a, int b)
{
return a < b ? a : b;
}
int min_of_3(int a, int b, int c)
{
int tmp = min_of_2(a, b);
return min_of_2(tmp, c);
}
int dp[201][201];//dp[i][j] 表示（字符串 source 前 i 个字符组成的子字符串）与（字符串 target 前 j 个字符组成的子字符串）的编辑距离
int Levenshtein_Distance(string source, string target)
{
//如果字符串 target 为空，则只需进行 source.size() 次删除操作
if (target.size() == 0)
{
return (int)source.size();
}
//如果字符串 source 为空，则只需进行 target.size() 次增加操作
if (source.size() == 0)
{
return (int)target.size();
}
//初始化第一列，可理解为（字符串 source 前 i 个字符组成的子字符串）与（空的字符串 target）的编辑距离，即 i 次删除操作
for (int i(0); i <= source.size(); ++i)
{
dp[i][0] = i;
}
//初始化第一行，可理解为（空的字符串 source）与（字符串 target 前 j 个字符组成的子字符串）的编辑距离，即 i 次增加操作
for (int i(0); i <= target.size(); ++i)
{
dp[0][i] = i;
}
for (int i(1); i <= source.size(); ++i)
{
for (int j(1); j <= target.size(); ++j)
{
if (source[i - 1] == target[j - 1])
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
dp[i][j] = min_of_3(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);
}
}
}
return dp[source.size()][target.size()];
}
int main()
{
string source, target;
while (cin >> source >> target)
{
cout << Levenshtein_Distance(source, target) << endl;
}
return 0;
}