如下表所示：
1.第一行以及第一列的单元格：
1）第一行：
遍历seq1中的每个字母，使每个字母与seq2的第1个字母比较：
（1）如果从来没有发生过相等事件，则变换次数加1；
（2）若第一次相等，则变换次数不变；
（3）若已经发生过相等事件，则不管接下来会不会发生相等事件，变换次数都加1。
2）第一列
遍历seq2中的每个字母，使每个字母与seq1的第1个字母比较
方法通1）。
2.其它单元格
每个单元格可由其左方，上方，左上方的单元格变换而来。
1）左方：seq1变换到seq2增加了一个字母，变换次数加1；
2）上方：seq1变换到seq2减少了一个字母，变换次数加1；
3）左上方：seq1变换到seq2替换了一个字母，这时分为两种情况：
（1）替换前的字母与替换后的字母不一样：变换次数加1
（2）替换前的字母与替换后的字母一样：变换次数不变
则sea变换到eat如上图所示：
则Sartuday变换到Sunday如上图箭头所示：
seq1->减a，变换次数加1->减t，变换次数加1->替换u为u，变换次数不变->替换r为n,变换次数加1
->分别替换d,a,y为d,a,y，变换次数三次不变
故变换次数为：加1->加1->不变->加1->不变->不变->不变
故变换次数共为3次
代码如下：
public class Convertion { private int[][]table; public int minDistance(String word1, String word2) { int row = word1.length(); int column = word2.length(); if(row==0) return column; if(column==0) return row; table = new int[row][column]; //判断word1的第i个字母与word2的第一个字母是否没有发生相等事件 boolean flag = true; //易得出第一列的值 int value = 0; for(int i=0;i<row;++i){ if(flag&&word1.charAt(i)==word2.charAt(0)){ table[i][0] = value; flag = false; }else table[i][0] = ++value; } //判断word2的第i个字母与word1的第一个字母是否没有发生相等事件 flag = true; //易得出第一行的值 value = 0; for(int i=0;i<column;++i){ if(flag&&word2.charAt(i)==word1.charAt(0)){ table[0][i] = value; flag = false; }else table[0][i] = ++value; } //从左到右，从上到下得出剩下的值 for(int i=1;i<row;++i) for(int j=1;j<column;++j){ //得出左、上、左上中的最小值 int adjacentMin = findMin(table[i-1][j],table[i][j-1],table[i-1][j-1]); //如果为左上且替换后字母与原来一致，则变换次数为最小值不变，否则为最小值+1 if(adjacentMin==table[i-1][j-1]&&word1.charAt(i)==word2.charAt(j)) --adjacentMin; table[i][j] = ++adjacentMin; } return table[row-1][column-1]; } private int findMin(int a,int b,int c){ int temp = a; if(b<temp) temp = b; if(c<temp) temp = c; return temp; } @Test public void test(){ System.out.println(minDistance("sea","eat")); for(int i=0;i<table.length;++i){ for(int j=0;j<table[0].length;++j) System.out.print(table[i][j]+" "); System.out.println(); } } }