代码随想录算法训练营第三十九天 | 动态规划 Part12

701 字

4 分钟

代码随想录算法训练营第三十九天 | 动态规划 Part12

2025-07-25

算法

动态规划、子序列问题

/

LeetCode

/

Python

115. 不同的子序列#

LeetCode 115. Distinct Subsequences

解题思路

定义：dp[i][j] 表示 s[0..i-1] 中子序列等于 t[0..j-1] 的个数。

初始化：当 j=0 时，空字符串是任何字符串的子序列，dp[i][0] = 1
状态转移：
- 如果 s[i-1] == t[j-1]：两种情况
  - 匹配当前字符：dp[i-1][j-1]
  - 不匹配当前字符：dp[i-1][j]
  - 总和：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
- 如果 s[i-1] != t[j-1]：只能跳过 s[i-1]，dp[i][j] = dp[i-1][j]

1
class Solution:
2
    def numDistinct(self, s: str, t: str) -> int:
3
        m, n = len(s), len(t)
4
        dp = [[0] * (n + 1) for _ in range(m + 1)]
5

6
        # 初始化：t为空字符串，所有s前缀都能匹配出1个空串
7
        for i in range(m + 1):
8
            dp[i][0] = 1
9

10
        # 状态转移
11
        for i in range(1, m + 1):
12
            for j in range(1, n + 1):
13
                if s[i - 1] == t[j - 1]:
14
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
15
                else:
16
                    dp[i][j] = dp[i - 1][j]
17

18
        return dp[m][n]

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

LeetCode 583. Delete Operation for Two Strings

解题思路

最优解法是基于最长公共子序列（LCS）
- 删除操作次数 = len(word1) + len(word2) - 2 * lcs(word1, word2)
此处提供的是另一种动态规划解法，模拟删除操作：

定义：dp[i][j] 表示将 word1[0..i-1] 和 word2[0..j-1] 变成相同所需的最少删除操作数。

初始化：
- dp[i][0] = i：将 word1 的前 i 个字符全删掉
- dp[0][j] = j：将 word2 的前 j 个字符全删掉
状态转移：
- 如果字符相同：dp[i][j] = dp[i-1][j-1]
- 如果不同：可以删掉 word1[i-1] 或 word2[j-1]，也可以两个都删
  - dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2)

1
class Solution:
2
    def minDistance(self, word1: str, word2: str) -> int:
3
        m, n = len(word1), len(word2)
4
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
5

6
        # 初始化
7
        for i in range(m + 1):
8
            dp[i][0] = i
9
        for j in range(n + 1):
10
            dp[0][j] = j
11

12
        # 状态转移
13
        for i in range(1, m + 1):
14
            for j in range(1, n + 1):
15
                if word1[i - 1] == word2[j - 1]:
16
                    dp[i][j] = dp[i - 1][j - 1]
17
                else:
18
                    dp[i][j] = min(
19
                        dp[i - 1][j] + 1,      # 删除 word1[i-1]
20
                        dp[i][j - 1] + 1,      # 删除 word2[j-1]
21
                        dp[i - 1][j - 1] + 2   # 两个都删
22
                    )
23

24
        return dp[m][n]

72. 编辑距离#

LeetCode 72. Edit Distance

解题思路

定义：dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 的最小操作数。

初始化：
- dp[i][0] = i：将 word1 的前 i 个字符全部删除
- dp[0][j] = j：将 word2 的前 j 个字符全部插入
状态转移：
- 如果字符相等：dp[i][j] = dp[i-1][j-1]
- 如果字符不同：
  - 插入：dp[i][j-1] + 1
  - 删除：dp[i-1][j] + 1
  - 替换：dp[i-1][j-1] + 1

1
class Solution:
2
    def minDistance(self, word1: str, word2: str) -> int:
3
        m, n = len(word1), len(word2)
4
        dp = [[0] * (n + 1) for _ in range(m + 1)]
5

6
        # 初始化
7
        for i in range(1, m + 1):
8
            dp[i][0] = i
9
        for j in range(1, n + 1):
10
            dp[0][j] = j
11

12
        # 状态转移
13
        for i in range(1, m + 1):
14
            for j in range(1, n + 1):
15
                if word1[i - 1] == word2[j - 1]:
16
                    dp[i][j] = dp[i - 1][j - 1]
17
                else:
18
                    dp[i][j] = min(
19
                        dp[i - 1][j - 1],  # 替换
20
                        dp[i - 1][j],      # 删除
21
                        dp[i][j - 1]       # 插入
22
                    ) + 1
23

24
        return dp[m][n]