【LeetCode】动态规划—115. 不同的子序列（附完整Python/C++代码）

动态规划—115. 不同的子序列

• 前言
• 题目描述
• 基本思路
  • 1. 问题定义
  • 2. 理解问题和递推关系
  • 3. 解决方法
  • • 3.1 动态规划方法
    • 3.2 空间优化的动态规划
  • 4. 进一步优化
  • 5. 小总结
• 代码实现
• • Python
  • • Python3代码实现
    • Python 代码解释
  • C++
  • • C++代码实现
    • C++ 代码解释
    • • 1. 变量定义:
      • 2. 初始化:
      • 3. 动态规划状态转移:
      • 4. 返回结果:
• 总结:

前言

在字符串处理的领域，不同子序列问题是一个经典的挑战，涉及到如何计算一个字符串的所有不同子序列以匹配另一个字符串。通过动态规划方法，我们能够有效地找出字符串之间的匹配数量，为更复杂的字符串问题提供解决方案。本文将详细介绍这一问题的思路、解决方法以及相应的 Python 和 C++ 实现代码。

题目描述

在这里插入图片描述

基本思路

1. 问题定义

不同子序列问题要求我们计算字符串

中有多少个不同的子序列等于字符串

。子序列是通过删除字符串中的某些字符（可以不删除任何字符）而形成的序列。

2. 理解问题和递推关系

• 我们可以定义一个二维数组

，表示字符串

的前

个字符与字符串

的前

个字符形成的不同子序列的数量。

• 递推关系如下：
  • 如果

  s[i-1]==t[j-1]

  ，则

  d p[i][j]=d p[i-1][j-1]+d p[i-1][j]

  。这表示我们可以选择将

  s[i-1]

  作为

  t[j-1]

  的一部分，或者不选择它。

  • 如果

  s[i-1]!=t[j-1]

  , 则

  d p[i][j]=d p[i-1][j]

  。这表示我们只能忽略

  s[i-1]

  来继续匹配

  t[j-1]

  。

3. 解决方法

3.1 动态规划方法

1. 创建一个二维数组

，大小为

，其中

是字符串

的长度，

是字符串

的长度。

1. 初始化边界条件:

   \mathrm{dp}[0][0]=1

   ：两个空字符串是一个有效的子序列。

   d p[i][\theta]=1

   ：任何字符串

   s

   的前

   i

   个字符与空字符串匹配的方式只有一种，即删除所有字符。

   d p[0][j]=0

   ：空字符串无法匹配非空字符串。

2. 使用双重矿环填充 dp 数组，依赖于前面的状态。
3. 最终结果为

。

3.2 空间优化的动态规划

• 可以使用一维数组来优化空间复杂度，将 dp 数组从二维变为一维。

4. 进一步优化

• 使用一维数组可以减少内存使用，同时时间复杂度保持在

，适合处理中等规模的字符串。

5. 小总结

• 不同子序列问题通过动态规划有效计算出字符串之间的匹配数量。
• 理解该问题的解决方案有助于掌握动态规划的设计理念，并能够应用于类似的字符串匹配问题。

以上就是不同的子序列问题的基本思路。

代码实现

Python

Python3代码实现

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        # 创建dp数组
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 初始化边界条件
        for i in range(m + 1):
            dp[i][0] = 1  # 空字符串t的匹配方法

        # 填充dp数组
        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]

Python 代码解释

• 初始化：创建 dp 数组并设置边界条件，处理空字符串的匹配。
• 动态规划填充：通过双重循环遍历 s 和 t 的每个字符，依据字符相同与否来更新 dp 数组。
• 返回结果：最终返回 dp[m][n]，即字符串 s 中与 t 匹配的不同子序列数量。

C++

C++代码实现

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        // 使用unsigned long long类型来防止溢出
        vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));

        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;  // 空字符串t的匹配方法
        }

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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];  // 字符不同
                }
            }
        }

        // 返回不同子序列的数量，确保返回的结果是int类型
        return static_cast<int>(dp[m][n]);
    }
};

C++ 代码解释

• 初始化：创建 dp 数组并设置边界条件，处理空字符串的匹配情况。
• 动态规划填充：通过双重循环更新 dp 数组，依赖于当前字符的匹配状态。
• 返回结果：返回 dp[m][n]，即不同子序列的数量。

1. 变量定义:

字符串的长度。

字符串的长度。

一个二维动态规划数组，用于存储从

的前

个字符中选择与

的前

个字符匹配的子序列个数。

的值表示从

的前

个字符中有多少个不同子序列可以匹配

的前

个字符。

2. 初始化:

：当

是空字符串时，不管

是什么，只有一种方法可以匹配空字符串，即删除所有字符。因此，

。

：当

是空字符串而

不是空字符串时，不可能通过任何方式匹配，因此

。

3. 动态规划状态转移:

• 字符相同: 如果

，有两种选择：

1. 不使用

，即

，忽略

，继续用前面的字符来匹配

。

1. 使用

, 即

，让

和

匹配。

• 最终

，两者相加表示两种选择的总数。

• 字符不同: 如果

，只能忽略

，即

，表示继续用

的前

个字符来匹配

。

4. 返回结果:

• 最终结果保存在

中，它表示字符串

中有多少个不同的子序列与

完全匹配。

• 由于动态规划数组使用的是 unsigned long long 来避免溢出，但题目要求返回 int 类型的结果，因此最后使用 static_cast<int>将其转换为 int。

总结:

• 不同子序列问题是动态规划的一个重要应用，展示了如何通过状态转移方程来计算字符串之间的匹配。
• 理解该问题的解决方案可以帮助掌握动态规划的核心思想，并为处理其他类似问题提供借鉴。
• 本文提供的代码实现既清晰又高效，为学习和应用动态规划提供了实际示例。