经典动态规划问题，由一个字符串s通过以下三种方式变换成目的串t所需的最少的步骤数。
1.添加一个字符；2.删除一个字符；3.替换一个字符。
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
以二维数组d[i][j]表示由s[1...i]到t[1...j]的最少变换次数，如何得到d[i][j]，需要从之前的d[i][j-1], d[i-1][j], d[i-1][j-1]来的出，可以很容易的得出如下计算方式：
if s[i-1] == t[j-1] :这里注意是用下标做判断的
cost = 0;
else cost = 1;
d[i][j] = min(
d[i-1][j] + 1;(删除s[i]操作)，
d[i][j-1] + 1;(在原先的基础上添加一个与t[j]同样的字符)
d[i-1][j-1] + cost;（或者变换一个字符，或者不变）
);
d[0...i][0] = i, d[0][0...j] = j;(一个时做添加操作，一个是做删除操作)
int edit_distance(string str, string tar){
int len1 = str.size(), len2 = tar.size(), cost;
int d[len1+1][len2+1];
for(int i = 0; i <= len1; i++)
d[i][0] = i;
for(int i = 0; i <= len2; i++)
d[0][i] = i;
for(int i = 1; i <= len1; i++)
for(int j = 1; j <= len2; j++){
if(str[i-1] == tar[j-1]) cost = 0;
else cost = 1;
d[i][j] = min(min(d[i][j-1], d[i-1][j]) + 1, d[i-1][j-1] + cost);
}
return d[len1][len2];
}