自然语言处理（NLP）中。有一个基本问题就是求两个字符串的minimal Edit Distance, 也称Levenshtein distance。受到一篇Edit Distance介绍文章的启示。本文用动态规划求取了两个字符串之间的minimal Edit Distance. 动态规划方程将在下文进行解说。

1. what is minimal edit distance?

简单地说。就是仅通过插入(insert)、删除(delete)和替换(substitute)个操作将一个字符串s1变换到还有一个字符串s2的最少步骤数。熟悉算法的同学非常easy知道这是个动态规划问题。

事实上一个替换操作能够相当于一个delete+一个insert，所以我们将权值定义例如以下：

I  (insert)：1

D (delete)：1

S (substitute)：2

2. example:

intention->execution

Minimal edit distance：

delete i ; n->e ; t->x ; insert c ; n->u 求和得cost=8

3.calculate minimal edit distance dynamically

思路见凝视，这里D[i,j]就是取s1前i个character和s2前j个character所得minimal edit distance

三个操作动态进行更新：

D(i,j)=min { D(i-1, j) +1, D(i, j-1) +1 , D(i-1, j-1) + s1[i]==s2[j] ? 0 : 2}。中的三项分别相应D，I，S。（详见我同学的博客）

由于本题的替换操作权重相同为1。故字符不相等+1就可以。

public class Solution {

    public int minDistance(String word1, String word2) {

        //边界条件

        if(word1.length() == 0)

    		return word2.length();

    	if(word2.length() == 0)

    		return word1.length();

        /*

         * 本题用动态规划的解法

         * f[i][j]表示word1的前i个单词到word2前j个单词的最短距离

         * 状态转移方程：f[i][j] =

         */

        int[][] f = new int[word1.length()][word2.length()];

        boolean isEquals = false;//是否已经有相等

        for(int i = 0 ; i < word2.length(); i++){

            //假设相等，则距离不添加

            if(word1.charAt(0) == word2.charAt(i) && !isEquals){

                f[0][i] = i > 0 ? f[0][i-1]:0;//不能从0開始

                isEquals = true;

            }else{

                f[0][i] = i > 0 ? f[0][i-1]+1:1;

            }

        }

        isEquals = false;//是否已经有相等

        for(int i = 1 ; i < word1.length(); i++){

            //假设相等，则距离不添加

            if(word1.charAt(i) == word2.charAt(0) && !isEquals){

                f[i][0] =  f[i-1][0];//不能从0開始

                isEquals = true;

            }else{

                f[i][0] = f[i-1][0]+1;

            }

        }

        for(int i = 1; i < word1.length();i++){

            for(int j = 1; j < word2.length(); j++){

                if(word1.charAt(i) == word2.charAt(j)){

                    f[i][j] = f[i-1][j-1];//相等的话直接相等

                }else{

                    f[i][j] = f[i-1][j-1]+1;

                }

                //然后与从f[i-1][j]+1。f[i][j-1]+1比較，取最小值

                f[i][j] = Math.min(f[i][j],Math.min(f[i-1][j]+1,f[i][j-1]+1));

            }

        }

        return f[word1.length()-1][word2.length()-1];

    }

}