编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
sitten （k->s）
sittin （e->i）
sitting （->g）
所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
给出两个字符串a,b，求a和b的编辑距离。
这题要分三种情况考虑：
先设dp[i][j]为a中1~i的子串和b中1~j的子串的编辑距离。
第一种情况，（由常识可得）a中1~i的子串可以由a中1~i-1的子串加上a[i]得到，b中1~j的子串可以由b中1~j-1的子串加上b[j]得到。如果我们知道了dp[i-1][j-1]=k，且a[i] != b[j],那么dp[i][j]就可以是k+1，即在原基础上修改a[i]变成b[j]，多花费了1。如果a[i]== b[j]，那dp[i][j]还是k。
第二种情况，如果我们知道了dp[i-1][j]=k，那么我们可以考虑把a[i]删除掉，这样dp[i][j]就可以是k+1。
第三种情况，如果我们知道了dp[i][j-1]=k，那么我们可以考虑把b[j]添加到a[i]后面，这样dp[i][j]就可以是k+1。
综上，dp[i][j]取上述三种情况的最小值。
另外，这题可以做个小优化，由于dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]有关，可以把dp数组改成滚动数组dp[2][MAXN]，这样可以有效降低空间复杂度
代码测试处：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1183
参考代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <bitset> #define X first #define Y second #define clr(u,v); memset(u,v,sizeof(u)); #define in() freopen("data","r",stdin); #define out() freopen("ans","w",stdout); #define Clear(Q); while (!Q.empty()) Q.pop(); #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e3 + 10; const int INF = 0x3f3f3f3f; char str1[maxn], str2[maxn]; int dp[maxn][maxn];//dp[i][j]代表str1中1~i的子串变成str2中1~j的子串的最小花费 int main() { scanf("%s%s", str2 + 1, str1 + 1); int len1 = strlen(str1 + 1), len2 = strlen(str2 + 1); int Max = max(len1, len2); dp[0][0] = 0; for (int i = 1; i <= Max; i++) dp[i][0] = dp[0][i] = dp[i-1][0] + 1;//初始化 for (int i = 1; i <= len1; i++) for (int j = 1; j <= len2; j++) { dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);//假设dp[i][j-1]和dp[i-1][j]已知，那么我们只要在里面找个最小的，在末尾添加上一个字符就是答案了 dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (str1[i] != str2[j]));//dp[i-1][j-1]已知的话，可以把str1[i]变成str2[j],此时如果str1[i]==str2[j],就无需花费，否则花费1 } // for (int i = 0; i <= len1; i++) // { // for (int j = 0; j <= len2; j++) // printf("%d ", dp[i][j]); // printf(" "); // } printf("%d ", dp[len1][len2]); return 0; }