题目描述

给定一个字符串 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
^^^

样例

时间复杂度 ： O(mn)
空间复杂度 ： O(n)

思路：
类似01背包问题的更新方式。
dp[j]表示第j个字符为止的所有匹配数目。
则当遇到一个相匹配的字符时，则dp[j] = dp[j-1]+dp[j];（j要从后向前更新），即当前字符所有可能的匹配数为上
一字符所有可能匹配数加上本字符的匹配之前所有可能的匹配数。
扫描一次s串，每扫描到一个字符则在t中从后向前查询位置j，并更新其状态为dp[j] = dp[j]+dp[j-1];

class Solution {
public:
    int numDistinct(string s, string t) {
        int i, j, k;
        vector<long> dp(t.size(), 0);
        for (i = 0; i < s.size(); ++i) {
            int j = s.size()- 1;
            while (j!=-1&&(j = t.rfind(s[i], j)) >= 0) {

                if (j == 0) {
                    ++dp[j];
                }
                else {
                    dp[j] = dp[j - 1] + dp[j];
                }
                --j;
            }
        }
        return dp[t.size() - 1];
    }
};