LeetCode 72【动态规划】

class Solution { public int minDistance(String word1, String word2) { int w1len = word1.length(); int w2len = word2.length(); //定义dp数组的含义, 这里dp[i][j]的含义被定义为 Word1的前i个字符转换成Word2的前j个字符一共需要dp[i][j]步 int[][] dp = new int[w1len+1][w2len+1]; //这里就没必要定义dp[0][0]了。因为数组本身default value就是0。当然如果数组不是int，需要额外定义 //dp[0][0] = 0; //接着我们定义特殊情况 //i=0或者j=0。i\j为0意味着“从空字符串转”或者“转换到空字符串”需要多少步骤，答案显然是不为空的字符的长度。 //这里我们把i\j两种情况合并成一句话，反正总有一个是0，w1len + w2len就行了. if(w1len <= 0 || w2len <= 0){ return w1len + w2len; } //定义边界条件，dp问题一般都需要对数组边界额外定义，体现在二维数组中就是“上边界”和“左边界” //即w1/w2为空时的数据情况，这时候数组是 ix1 或者 1xj的情况，dp[i][0]唯一依赖于dp[i-1][0]，只比他多一步。同样的:dp[0][j]唯一依赖于dp[0][j-1] for (int i=1; i<=w1len; i++){ dp[i][0] = dp[i-1][0] + 1; } for (int j=1; j<=w2len; j++){ dp[0][j] = dp[0][j-1] + 1; } //接下来我们对剔除特殊情况后的数组进行数值填充。 //dp问题里，一般的情况下，在这里都是找出 dp[i][j]和dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]的关系。而且一般肯定是有关系的 //观察题目条件，给出了3种操作：插入、删除、替换，那么对应到dp[i][j]中就有3种方式。 //为了便于理解我们额外定义3个变量: x y z。 假设x->y最少需要n步，y->z只需要一步。 // 1.y->z需要一步插入操作，那么就是 n+1 // 2.y->z需要一步删除操作，那么就是 n+1 // 3.y->z需要一步替换操作，那么就是 n+1，字符相同的情况下为 n+0 //ok, 那么我们只需要math.min找出3者中的最小值即可 for(int i=1; i<=w1len; i++){ for(int j=1; j<=w2len; j++){ // 如果 word1的第i个字符和word2的第j个字符相同,那么说明最后一个字符不用替换，少了一步，否则需要额外加1步。注意：第‘x’个字符应该是word.charAt(x-1) int ijIsSame = word1.charAt(i-1)!=word2.charAt(j-1) ? 1 : 0; dp[i][j] = Math.min(Math.min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1] + ijIsSame); } } return dp[w1len][w2len]; } }