最近在做项目的过程中需要计算两个字符串之间的编辑距离，所谓编辑距离，就是讲其中一个串变成另一个串需要的做少的操作次数，允许的操作包括：在任意位置添加一个字符、修改一个字符、删除一个字符。例如：
s1="123456"
s2="234561"
s2要变成s1，需要在首位添加一个'1'，在末尾删除一个'1',共需要两次操作，所以s1和s2的编辑距离为2；
解决思路
设dis[i][j]表示s1的下标0到i的子串和s2的下标0到j的子串的编辑距离。
特殊情况：
显然dis[0][j]=j，dis[i][0]=i，此时其中一个串为空串，要将其变成另一个串则需要添加相应数量的字符。
一般情况，考虑三种操作：
- 在s2相应子串后面添加新字符使其等于s1[i]：则dis[i][j]=dis[i-1][j]+1;
- 删除s2相应子串的最后一个字符：dis[i][j]=dis[i][j-1]+1;
- 将s2相应的子串的最后一个字符改成s1相应子串最后一个字符：
此时要考虑两种情况：
1、s1[i]=s2[j]，此时不需要修改，dis[i][j]=dis[i-1][j-1]。
2、s1[i]!=s2[j]，此时需要一次修改，dis[i][j]=dis[i-1][j-1]+1;
综上，我们取三种情况中所求的距离最小的哪一个。
动态规划方程（edit即为为dis）：
其中：
//参考代码
public static int Levenshtein_dis(String s1,String s2){
int dis[][] = new int[s1.length()+1][s2.length()+1];
dis[0][0]=0;
for (int i=1;i<=s1.length();++i) dis[i][0]=i;
for (int j=1;j<=s2.length();++j) dis[0][j]=j;
for (int i=1;i<=s1.length();++i){
for (int j=1;j<=s2.length();++j){
int cost=1;
if (s1.charAt(i-1)==s2.charAt(j-1)) cost=0;
int min;
if (dis[i-1][j-1]+cost<dis[i][j-1]+1) min=dis[i-1][j-1]+cost;
else min=dis[i][j-1]+1;
if (min>dis[i-1][j]+1) min=dis[i-1][j]+1;
dis[i][j]=min;
}
}
return dis[s1.length()][s2.length()];
}
