动态规划

状态转移方程
f[i,j]={f[i−1,j]f[i−1,j]+f[i−1,j−1]if s[i]=t[j]f[i,j]=\begin{cases} f[i-1,j]\\ f[i-1,j]+f[i-1,j-1]&\text{if } s[i]=t[j] \end{cases}f[i,j]={f[i−1,j]f[i−1,j]+f[i−1,j−1]​if s[i]=t[j]​

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

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

class Solution {
public:int numDistinct(string s, string t) {int n = s.size(), m = t.size();s = ' ' + s, t= ' ' + t;vector> f(n+1,vector(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. 时间复杂度 : O(n×m)O(n\times m)O(n×m) ， nnn 是字符串 sss 的长度 ， mmm 是字符串 ttt 的长度，状态转移的时间复杂度 O(n×m)O(n\times m)O(n×m) 。
2. 空间复杂度 : O(n×m)O(n\times m)O(n×m) ， 所有状态的空间复杂度 O(n×m)O(n\times m)O(n×m) 。

AC