[数据结构与算法]不同的子序列（LeetCode-115）

不同的子序列（LeetCode-115）

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

示例 2：

提示：

• 0 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

思路

五部曲

1. dp[i][j] 含义

   • 以 $i?1$ 为结尾的字符串s子序列中出现以 $j?1$ 为结尾的字符串t的个数

2. 递推公式

   • 如果 $s[i?1]=t[j?1]$?

     • 一种方法是用 $s[i?1]$ 来匹配，个数为 $dp[i?1][j?1]$
     • 即使相等，就一定要用它匹配？举个例子 $s:bagg$ $t:bag$，$s[3]=s[2]$，可以选着用 $s[3]$ 进行匹配，也可以不选，那就是用 $dp[i?1][j]$

   • 如果二者不相等，肯定不能用 $s[i?1]$，所以 $dp[i][j]=dp[i?1][j]$

3. 数组初始化

   • dp[i][0] 表示出现空字符串的个数，只有一种方法，就是全删，所以等于一
   • dp[0][j] 表示空字符串出现以 $j?1$ 为结尾的字符串t的个数，只能为零
   • dp[0][0] 空字符串可以删除0个元素，出现空字符串t，所以为一

4. 遍历顺序

   • 从前往后

5. 测试用例

代码展示

class Solution
{
public:
    int numDistinct(string s, string t)
    {
        int n1 = s.size();
        int n2 = t.size();
        if (n1 < n2)
        {
            return 0;
        }

        vector<vector<uint64_t>> dp(n1 + 1, vector<uint64_t>(n2 + 1));
        dp[0][0] = 1;
        for (int i = 0; i < n1; i++)
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; 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];
                }
            }
        }
        return dp[n1][n2];
    }
};