题目地址 (opens new window)

  • 🙂 第一次练习 2020å¹´4月6日 动态规划的题,还没学到那里去,太难了。我丢。。。。直接看题解 (opens new window)
  • 😄 第二次练习

# 动态规划

优秀题解 (opens new window)

解题代码

public int minDistance(String word1, String word2) {
    char[] word1Array = word1.toCharArray();
    char[] word2Array = word2.toCharArray();

    int len1 = word1Array.length;
    int len2 = word2Array.length;

    // 多开一行一列是为了保存边界条件,即字符长度为 0 的情况,这一点在字符串的动态规划问题中比较常见
    int[][] dp = new  int[len1 + 1][len2 + 1];

    // 初始化:当 word 2 长度为 0 时,将 word1 的全部删除
    for(int i = 1; i <= len1; i ++) {
        dp[i][0] = i;
    }

    // 当 word1 长度为 0 时,就插入所有 word2 的字符
    for(int j = 1; j <= len2; j ++) {
        dp[0][j] = j;
    }

    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            // 这是最佳情况
            if (word1Array[i] == word2Array[j]) {
                dp[i + 1][j + 1] = dp[i][j];
                continue;
            }

            // 否则在以下三种情况中选出步骤最少的,这是「动态规划」的「最优子结构」
            // 1、在下标 i 处插入一个字符
            int insert = dp[i + 1][j] + 1;
            // 2、替换一个字符
            int replace = dp[i][j] + 1;
            // 3、删除一个字符
            int delete = dp[i][j + 1] + 1;

            dp[i + 1][j + 1] = Math.min(Math.min(insert, replace), delete);
        }
    }

    return dp[len1][len2];
}

# 易错点

  • 易错项 1
最后编辑时间: 7/14/2020, 9:21:47 AM