算法训练营day46 | {115.不同的子序列, 583.两个字符串的删除操作, 72.编辑距离}

第九章动态规划-part12，编辑距离是用动规来解决的经典题目。

115. 不同的子序列

1.1 解题分析

s = “babgbag”
t = “bag”

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示以i - 1结尾的s中有以j - 1结尾的t的个数是dp[i][j]个。
  2. 递推公式：
    • 如果s[i - 1]和t[j - 1]相等，继续比较s[i-2]和t[j-2]，或者对s做删除（减法），比如s=”bagg”，比较s[i-2]和t[j-1]是否相等。
    • if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 2][j - 2] + dp[i - 1][j]
    • else dp[i][j] = dp[i - 1][j]
  3. 遍历顺序：从左到右，从上到下。
  4. 打印dp数组。

1.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int numDistinct(String s, String t) {
        int x = s.length() + 1;
        int y = t.length() + 1;
        int[][] dp = new int[x][y];
        for (int i = 0; i < x; i++) dp[i][0] = 1;
        for (int j = 1; j < y; j++) dp[0][j] = 0;

        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[x - 1][y - 1];
    }
}

583. 两个字符串的删除操作

2.1 解题分析

s = “sea”
t = “eat”

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示以i-1结尾的word1和以j-1结尾的word2相同所需的最小步数
  2. 递推公式：
    • if (s[i - 1] == t[j - 1]) d[i][j] = dp[i - 1][j - 1]
    • else dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i -1][j - 1] + 2)
  3. dp数组初始化：
    • dp[i][0] = i
    • dp[0][j] = j
  4. 遍历顺序：从左到右，从上到下。
  5. 打印dp数组。

2.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDistance(String word1, String word2) {
        int x = word1.length() + 1;
        int y = word2.length() + 1;
        int[][] dp = new int[x][y];
        for (int i = 0; i < x; i++) dp[i][0] = i;
        for (int j = 0; j < y; j++) dp[0][j] = j;

        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[x - 1][y - 1];
    }
}

解法二：求最长公共子序列的和，然后，word1.size + word2.size - longestSubLength * 2

72. 编辑距离

3.1 解题分析

很经典的dp题目，用动态规划巧妙地解决解决编辑距离问题。

word1 = “horse”
word2 = “ros”

1
2
3
horse -> rorse h->r
rorse -> rose  删除r
rose  -> ros   删除e

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示以i-1为结尾的word1和以j-1为结尾的word2相同的最少操作次数
  2. 递推公式：
    • if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]
    • else 不相同的话，可以进行删除、添加、替换操作，注意删除操作等价于添加操作，所以合并
    • dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)
  3. dp数组初始化：
    • dp[i][0] = i
    • dp[0][j] = j
  4. 遍历顺序：从左到右，从上到下。
  5. 打印dp数组。

3.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDistance(String word1, String word2) {
        int x = word1.length() + 1;
        int y = word2.length() + 1;
        int[][] dp = new int[x][y];
        for (int i = 0; i < x; i++) dp[i][0] = i;
        for (int j = 0; j < y; j++) dp[0][j] = j;

        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[x - 1][y - 1];
    }
}

4. 今日收获

Leetcode > 动态规划
#Java #代码随想录
算法训练营day46 | {115.不同的子序列, 583.两个字符串的删除操作, 72.编辑距离}
http://paopaotangzu.xyz/cn/day46_leetcode/
作者
PROTON TANG
发布于
2026年2月6日
许可协议