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

问题描述

给定一个字符串 s 和一个字符 t，返回在 s 中是 t 的子序列的个数。

子序列 是指一个字符串可以通过删除某些字符（不改变剩余字符的顺序）来得到另一个字符串。

示例：

输入: s = "abab", t = "ab"
输出: 2
解释: "ab" 和 "abab" 都是 "ab" 的子序列。

解决方法

这个问题可以使用动态规划来解决。以下是解决这个问题的步骤：

  1. 定义状态：dp[i][j] 表示 s 的前 i 个字符中，是 t 的前 j 个字符子序列的个数。
  2. 初始化：dp[0][0] = 1，表示空字符串是空字符串的子序列。
  3. 状态转移方程：
    • 如果 s[i-1] == t[j-1]，则 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。
    • 如果 s[i-1] != t[j-1]，则 dp[i][j] = dp[i-1][j]。
  4. 计算结果：dp[len(s)][len(t)] 就是 s 中是 t 的子序列的个数。

代码示例

以下是 Python 代码示例：

def numDistinct(s, t):
    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]

# 测试
s = "abab"
t = "ab"
print(numDistinct(s, t))  # 输出: 2

扩展阅读

如果你对动态规划感兴趣，可以阅读更多关于动态规划的内容。以下是一些推荐的链接：

希望这个示例能帮助你更好地理解如何使用动态规划解决不同的子序列问题。😊

Dynamic Programming