思路：1.先通过暴力递归枚举出所有解，找出递归过程中的冗余
2.设计存储空间保留冗余过程
3.递归式
4.自底向上写出递推式
首先把问题拆解成子问题，word1转成word2,只能有三种方式，插入，删除，修改:
1.删除,自己的长度减一 search(n-1,m);
2.插入,自己插入一个数，能和word2匹配，所以word2的长度减一 search(n,m-1);
3.修改,不一致的情况下，word1的改成word2，自己长度减一，还能和word2匹配，word2长度也减一 search(n-1,m-1);
4.边界条件处理：word1,word2同时没有数可以比较才能完全匹配 return 0;
word1已经为空，word2不为空，word1通过插入变成word2 search(n,m-1)+1;
word1不为空，word2为空,word1通过删除变成word2 search(n-1,m)+1;
/* 题目：编辑距离 * @author:zhn * 计划搜索算法，核心if(f[n][m] 算过) return f[n][m]; * 求得word1通过最少的变化达到word2，所以要求的是Math.min最小值 * 只有三个操作，插入，删除，修改：1.删除,自己的长度减一 search(n-1,m); * 2.插入,自己插入一个数，能和word2匹配，所以word2的长度减一 search(n,m-1); * 3.修改,不一致的情况下，word1的改成word2，自己长度减一，还能和word2匹配，word2长度也减一 search(n-1,m-1); * 4.边界条件处理：word1,word2同时没有数可以比较才能完全匹配 return 0; * word1已经为空，word2不为空，word1通过插入变成word2 search(n,m-1)+1; * word1不为空，word2为空,word1通过删除变成word2 search(n-1,m)+1; * */ public static int search(int n,int m) { if(n < 0 && m >= 0) //word1已经为空，word2不为空，word1通过插入变成word2 return search(n,m-1)+1; if(n >= 0 && m < 0) return search(n-1,m)+1; //word1不为空，word2为空,word1通过删除变成word2 if(n < 0 && m < 0) return 0; if(f[n][m] > 0 ) return f[n][m]; int a = 1000,b = 1000,c = 1000; if(x[n] == y[m]) a = search(n-1,m-1); //两个值匹配，继续匹配下一层 else a = search(n-1,m-1) + 1; //两个值不匹配，插入删除修改选一种最小的 b = search(n-1,m) + 1; c = search(n,m-1) + 1; f[n][m] = (a<b?a:b)<c?(a<b?a:b):c; return f[n][m]; } /* * @author:zhn * 把计划搜索改成自底向上的递推 * 首先处理边界条件：1.两者皆为空，return 0 * 2.一个空，一个不空，word1-->word2 通过插入或删除变过去 * 3.有了上述边界f[0][0],f[x][0],f[0][y]中的0就表示字符串为空，并不是一个字符，所以整个二维数组边界要扩张1 * 4.申请二维数组f[len1+1][len2+1] * 递推式（状态转移方程）改写成递推 */ public static int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); x = new char[len1]; y = new char[len2]; x = word1.toCharArray(); y = word2.toCharArray(); f = new int[len1+1][len2+1]; if(len1 == 0 && len2 == 0) f[len1][len2] = 0; for(int i=1;i<=len1;i++) //word1不为空，word2为空,word1通过删除变成word2 f[i][0] = i; for(int i=1;i<=len2;i++) //word1不为空，word2为空,word1通过删除变成word2 f[0][i] = i; for(int i=1;i<=len1;i++){ for(int j=1;j<=len2;j++){ if(x[i-1] == y[j-1]) f[i][j] = (f[i-1][j-1] < f[i-1][j] + 1? f[i-1][j-1] : f[i-1][j] + 1) < f[i][j-1] + 1 ? (f[i-1][j-1] < f[i-1][j] + 1? f[i-1][j-1] : f[i-1][j] + 1) : f[i][j-1] + 1; else f[i][j] =(f[i-1][j-1]+1 < f[i-1][j]+1 ? f[i-1][j-1]+1 : f[i-1][j]+1) < f[i][j-1]+1 ? (f[i-1][j-1]+1 < f[i-1][j]+1 ? f[i-1][j-1]+1 : f[i-1][j]+1) : f[i][j-1]+1; } } return f[len1][len2]; }