力扣(LeetCode)115. 不同的子序列(C++)

动态规划

状态转移方程
f [ i , j ] = { f [ i − 1 , j ] f [ i − 1 , j ] + f [ i − 1 , j − 1 ] if  s [ i ] = t [ j ] f[i,j]=

f[i,j]={f[i−1,j]f[i−1,j]+f[i−1,j−1]​if s[i]=t[j]​

无论选不选 $s[i]$ ， $f[i][j]$ 一定包含 $f[i-1][j]$ ，即 $s[1$~$i-1]$ 含有 $t[1$~$j]$ 的方案全部顺延过来。

如果选 $s[i]$ ，仅当 $s[i]=t[j]$ ， $f[i][j]$ 包含 $f[i-1][j-1]$ 。即 $s[1$~$i-1]$ 生成 $t[1$~$j-1]$ 的方案全部顺延过来。

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        s = ' ' + s, t= ' ' + t;
        vector<vector<long long>> f(n+1,vector<long long>(m+1,0));
        for(int i = 0;i<=n;i++) f[i][0] = 1;
        for(int i = 1; i<=n;i++)
            for(int j = 1;j<=m;j++){
                f[i][j] = f[i-1][j];
                if(s[i]==t[j]) f[i][j]+=f[i-1][j-1];
                f[i][j]%=INT_MAX;
            }
        return f[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1. 时间复杂度 : $O(n\times m)$ ， $n$ 是字符串 $s$ 的长度 ， $m$ 是字符串 $t$ 的长度，状态转移的时间复杂度 $O(n\times m)$ 。
2. 空间复杂度 : $O(n\times m)$ ， 所有状态的空间复杂度 $O(n\times m)$ 。

AC