含有不同子序列的数目

发布时间 : 2025-12-29 16:59

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

考虑DP
对于t，从0到t的每一位都分别截取子串
dp[i][j] 表示在s的i位置t的前j位子串的数目
可以得到转移方程：
如果某一位匹配上了
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

int mod = 1e9+7;
class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(),m = t.size();
        int dp[n+1][m+1];
        memset(dp,0,sizeof(dp));
        for(int i = 0; i <= n; i++) {
            dp[i][0] = 1; 
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if(s[i-1] == t[j-1]) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1])%mod;
                }
            }
        }
        return dp[n][m];
    }
};

空间压缩

int mod = 1e9+7;

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<int> dp(m + 1, 0);
        dp[0] = 1;  // 初始化dp[0], 空字符串t和任何字符串s有一个匹配

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) { // 从后往前计算，避免覆盖前一轮的dp[j-1]
                if (s[i - 1] == t[j - 1]) {
                    dp[j] = (dp[j] + dp[j - 1]) % mod;
                }
            }
        }
        return dp[m];
    }
};