LeetCode 动态规划问题 - 不同的子序列

动态规划（Dynamic Programming，简称 DP）是解决许多算法问题的强大工具。在 LeetCode 上，有很多经典的 DP 问题。今天我们来探讨一个 DP 经典问题：不同的子序列。

不同的子序列是指给定一个字符串 s 和一个字符串 t，找出 s 中所有可能的子序列中，与 t 相同的子序列的数量。

代码示例

以下是一个使用 Python 语言实现的示例：

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[m][n]

扩展阅读

如果你对动态规划感兴趣，可以阅读我们网站上的更多相关内容：

• 动态规划基础
• LeetCode 动态规划题目集锦

图片展示

Dynamic Programming