【算法|动态规划No.22】leetcode115. 不同的子序列

点击直接跳转到该题目

1️⃣题目描述

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 1 0 9 10^{9} 109 + 7取模。

示例1：

实例2：

注意：

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

2️⃣题目解析

状态表示：

• dp[i][j]：s字符串[0,i]区间的子串中含有多少个t字符串[0,j]区间内的子串

状态转移方程（根据s字符串中子序列的最后一个位置是否包含s[j]）：

• 包含s[j]时：如果t[i] == s[j]，则dp[i][j] = dp[i - 1][j - 1]
• 不包含s[j]时：dp[i][j] += dp[i ][j - 1]

3️⃣解题代码

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

最后就通过啦！！！