Leetcode 115

115. 不同的子序列 - 力扣（LeetCode）

115. 不同的子序列 - 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。   示例 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 <= s.length, t.length <= 1000 * s 和 t 由英文字母组成

https://leetcode.cn/problems/distinct-subsequences/

题目要求

给定字符串s和t，求s的子序列中t出现的总次数

核心算法和原理

• dp数组[i, j]定义为s[i…]中出现t[j…]的子序列的数量

• 从i这个维度向下线性遍历

• 解释下面那项：当我s[i]和t[j]相同时，我可以把状态转移到匹配成功(i+1, j+1)的情况，也可以不匹配这项，让s[i]前面的字符去匹配t[j]，这样穷尽了所有可能

• 很容易压成一维，反着遍历第二层就行

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int LL = 1000000007;
        int ns = s.size();
        int nt = t.size();
        vector<int> dp(nt + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < ns; i++) {
            for (int j = nt; j >= 1; j--) {
                if (t[j - 1] == s[i]) {
                    dp[j] = (dp[j] + dp[j - 1]) % LL;
                }
            }
        }
        return dp[nt];
    }
};