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

前言

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

题目描述

基本思路

1. 问题定义

不同子序列问题要求我们计算字符串 $s$ 中有多少个不同的子序列等于字符串 $t$ 。子序列是通过删除字符串中的某些字符（可以不删除任何字符）而形成的序列。

2. 理解问题和递推关系

• 我们可以定义一个二维数组 $dp[i][j]$ ，表示字符串 $s$ 的前 $i$ 个字符与字符串 $t$ 的前 $j$ 个字符形成的不同子序列的数量。
• 递推关系如下：
  • 如果 $s[i-1]==t[j-1]$ ，则 $dp[i][j]=dp[i-1][j-1]+dp[i-1][j]$ 。这表示我们可以选择将 $s[i-1]$ 作为 $t[j-1]$ 的一部分，或者不选择它。
  • 如果 $s[i-1]!=t[j-1]$, 则 $dp[i][j]=dp[i-1][j]$ 。这表示我们只能忽略 $s[i-1]$ 来继续匹配 $t[j-1]$ 。

3. 解决方法

3.1 动态规划方法

1. 创建一个二维数组 $dp$ ，大小为 $(m+1)\times (n+1)$ ，其中 $m$ 是字符串 $s$ 的长度， $n$ 是字符串 $t$ 的长度。
2. 初始化边界条件:
   • $\mathrm{dp}[0][0]=1$ ：两个空字符串是一个有效的子序列。
   • $dp[i][\theta ]=1$ ：任何字符串 $s$ 的前 $i$ 个字符与空字符串匹配的方式只有一种，即删除所有字符。
   • $dp[0][j]=0$ ：空字符串无法匹配非空字符串。
3. 使用双重矿环填充 dp 数组，依赖于前面的状态。
4. 最终结果为 $dp[m][n]$ 。

3.2 空间优化的动态规划

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

4. 进一步优化

• 使用一维数组可以减少内存使用，同时时间复杂度保持在 $O(m\ast n)$ ，适合处理中等规模的字符串。

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. 变量定义:

• $m：s$ 字符串的长度。
• $n：t$ 字符串的长度。
• $dp：$一个二维动态规划数组，用于存储从 $s$ 的前 $i$ 个字符中选择与 $t$ 的前 $j$ 个字符匹配的子序列个数。 $dp[i][j]$ 的值表示从 $s$ 的前 $i$ 个字符中有多少个不同子序列可以匹配 $t$ 的前 $j$ 个字符。

2. 初始化:

• $dp[i][\theta ]=1$ ：当 $t$ 是空字符串时，不管 $s$ 是什么，只有一种方法可以匹配空字符串，即删除所有字符。因此， $dp[i][0]=1$ 。
• $dp[0][j]=0$ ：当 $s$ 是空字符串而 $t$ 不是空字符串时，不可能通过任何方式匹配，因此 $\mathrm{dp}[0][j]=0$ 。

3. 动态规划状态转移:

• 字符相同: 如果 $s[i-1]==\mathrm{t}[j-1]$ ，有两种选择：

1. 不使用 $s[i-1]$ ，即 $dp[i][j]=dp[i-1][j]$ ，忽略 $s[i-1]$ ，继续用前面的字符来匹配 $t[j]$ 。
2. 使用 $s[i-1]$, 即 $dp[i][j]=dp[i-1][j-1]$ ，让 $s[i-1]$ 和 $t[j-1]$ 匹配。

• 最终 $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]$ ，表示继续用 $s$ 的前 $i-1$ 个字符来匹配 $t[j]$ 。

4. 返回结果:

• 最终结果保存在 $dp[m][n]$ 中，它表示字符串 $s$ 中有多少个不同的子序列与 $t$ 完全匹配。
• 由于动态规划数组使用的是 unsigned long long 来避免溢出，但题目要求返回 int 类型的结果，因此最后使用 static_cast<int>将其转换为 int。

---

总结:

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

原文地址：https://blog.csdn.net/AlbertDS/article/details/142765503

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！