题目内容

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

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

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

示例

示例 1：

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

提示

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

题解

本题考查动态规划。具体来说，对题目我们可以换一种方式来理解，即使用S中的字符按顺序匹配T中的字符，求有多少种方式匹配成功。

具体动归思路如下：

1、状态表示

定义F[i][j] 表示S串1到i的所有和T串1到j相等的子序列的所有匹配方式的数量。

2、状态计算

（1）当选择S[i]时，F[i][j] = F[i-1][j-1]

（2）当不选择S[i]，F[i][j] = F[i-1][j]

时间复杂度为O(n^2)。

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(),m = t.size();//求两个串的长度
        s = ' ' + s, t = ' '+t;//保证下标从1开始
        vector<vector<unsigned long long>> f(n+1,vector<unsigned long long>(m+1));//为了防止计算中间过程中的边界溢出
        for(int i = 0;i<=n;i++) f[i][0] = 1;//初始化当T串长度为0时的情况，各情况数量均为1
        for(int i = 1;i<=n;i++){
            for(int j = 1; j<=m; j++){
                f[i][j] = f[i-1][j];
                if(s[i] == t[j]) f[i][j] += f[i-1][j-1];
            }
        }
        return f[n][m];
    }
};