526互联

LeetCode 115. 不同的子序列

发布时间 2023-04-15 14:33:02作者: 穿过雾的阴霾
class Solution {
public:
    long long f[1010][1010];//f[i][j]表示s前i个字符得到t前j个字符的所有方案
    int numDistinct(string s, string t) {
        f[0][0]=1;
        int n=s.size(),m=t.size();
        s=' '+s;t=' '+t;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
            {
                f[i][j]=f[i-1][j];
                if(j&&s[i]==t[j])  
                    f[i][j]+=f[i-1][j-1]%INT_MAX;
            }
        return f[n][m];
    }
};