力扣第115题：不同的子序列 — C语言解法

力扣第115题：不同的子序列 — C语言解法

题目描述

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

子序列 是由字符串中删除一些字符（可以不删除任何字符）得到的一个新字符串。

说明：

• 字符串 s 和 t 的长度均不超过 $1000$。
• 一个子序列是由删除零个或多个字符而得到的字符串。

解题思路

这道题目要求我们计算字符串 t 在字符串 s 中出现的不同子序列的个数。子序列的匹配可以是不连续的，但必须按顺序匹配。

动态规划（Dynamic Programming）

这是一道典型的动态规划问题。设 dp[i][j] 表示字符串 s 的前 $i$ 个字符中，字符串 t 的前 $j$ 个字符的不同子序列的个数。

状态转移方程

1. 当字符匹配时（$s[i-1]==t[j-1]$）：

   • 我们有两种选择：
     • 包含当前字符：即在当前字符 s[i-1] 匹配到 t[j-1] 后，继续计算剩余部分：dp[i-1][j-1]。
     • 不包含当前字符：即忽略当前字符 s[i-1]，继续计算：dp[i-1][j]。
   • 所以状态转移方程为：
     $$dp[i][j]=dp[i-1][j-1]+dp[i-1][j]$$

2. 当字符不匹配时（$s[i-1]\ne t[j-1]$）：

   • 我们只能选择不包含当前字符 s[i-1]，即：
     $$dp[i][j]=dp[i-1][j]$$

边界条件

• dp[i][0] = 1：对于任何 $i$，空字符串 t 总能在字符串 s 中找到（即不选任何字符）。
• dp[0][j] = 0：对于任何 $j>0$，空字符串 s 无法包含任何非空字符串 t。

模运算

由于子序列的个数可能非常大，我们需要对结果进行取模运算。通常使用 $MOD=10^9+7$，它是一个大素数，可以避免整数溢出，并且在算法竞赛中常见。

代码实现

#include <stdio.h>
#include <string.h>

#define MOD 1000000007  // 定义常用的模数

// 动态规划实现：计算 t 在 s 中的不同子序列个数
long long numDistinct(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);

    // dp[i][j] 表示 s[0..i-1] 中 t[0..j-1] 的不同子序列个数
    long long dp[m + 1][n + 1];

    // 初始化 dp 数组
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;  // 空字符串 t 总能在任何 s 中找到
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 0;  // 非空字符串 t 不能在空字符串 s 中找到
    }

    // 填充 dp 数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[j - 1]) {
                // 如果 s[i-1] == t[j-1]，我们可以选择包含 s[i-1] 或不包含
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
            } else {
                // 如果 s[i-1] != t[j-1]，我们只能选择不包含 s[i-1]
                dp[i][j] = dp[i - 1][j] % MOD;
            }
        }
    }

    // 返回 dp[m][n]，即 s[0..m-1] 中 t[0..n-1] 的不同子序列个数
    return dp[m][n];
}

// 测试代码
int main() {
    char s[] = "rabbbit";
    char t[] = "rabbit";

    long long result = numDistinct(s, t);
    printf("Number of distinct subsequences: %lld\n", result);

    return 0;
}

代码解析

1. 定义模数

我们在代码中定义了常量 MOD = 1000000007，用于防止结果的溢出。每次更新 dp 数组时，我们都对当前值取模，确保它不会超出 long long 类型的最大值。

#define MOD 1000000007  // 定义常用的模数

2. 初始化 dp 数组

在动态规划中，我们使用一个二维数组 dp 来存储不同子序列的计数。dp[i][j] 表示在 s[0..i-1] 中找到 t[0..j-1] 的不同子序列的个数。我们初始化 dp[i][0] = 1，因为空字符串 t 总是能够在 s 中找到（即不选择任何字符）。同时，对于任何 j > 0，dp[0][j] = 0，因为非空字符串 t 无法在空字符串 s 中找到。

for (int i = 0; i <= m; i++) {
    dp[i][0] = 1;  // 空字符串 t 总能在任何 s 中找到
}
for (int j = 1; j <= n; j++) {
    dp[0][j] = 0;  // 非空字符串 t 不能在空字符串 s 中找到
}

3. 填充 dp 数组

我们按照动态规划的思路，遍历 s 和 t 的每个字符，更新 dp[i][j]。如果 s[i-1] == t[j-1]，我们可以选择包含当前字符或不包含它，更新为：
$$dp[i][j]=dp[i-1][j-1]+dp[i-1][j]$$
否则，我们只能选择不包含当前字符：
$$dp[i][j]=dp[i-1][j]$$

每次更新时，我们都对结果取模，防止溢出。

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]) % MOD;
        } else {
            dp[i][j] = dp[i - 1][j] % MOD;
        }
    }
}

4. 返回结果

最终，dp[m][n] 存储的是在 s[0..m-1] 中，t[0..n-1] 的不同子序列的个数。

return dp[m][n];

5. 测试代码

在 main 函数中，我们测试了 s = "rabbbit" 和 t = "rabbit" 的情况，输出了结果：

long long result = numDistinct(s, t);
printf("Number of distinct subsequences: %lld\n", result);

时间复杂度与空间复杂度

• 时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 分别是字符串 s 和 t 的长度。我们需要填充一个 $m\times n$ 的动态规划数组。
• 空间复杂度：$O(m\times n)$，用于存储动态规划数组 dp。

由于每次更新 dp[i][j] 时的计算都是常数时间，因此总时间复杂度为 $O(m\times n)$。