题目地址：https://leetcode-cn.com/problems/distinct-subsequences/description/
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
比如：S = "rabbbit", T = "rabbit"，则输出 3。
思路一
最简单直接的思路就是暴力枚举 S 的所有子序列，然后逐一比较，时间复杂度为 $O(2^n)$，显然是不可接受的。
思路二
一个比较容易想到的思路是递归求解，先在 S 中找到 T 的第一个字符，然后每找到一个就从 S 的下一个位置开始递归找 T 的下一个字符，递归的边界条件就是 T 的下标为 T 的长度，这时候说明找到了一个子序列，返回 1，然后将结果累加即可。代码如下：
函数中 s_i 和 t_i 表示从 s 的下标为 s_i 的地方开始查找 t 下标为 t_i 的字符，初始调用即为 work(s, t, 0, 0)。
vector<vector<int>> cache;
int numDistinctR(string & s, string & t, size_t s_i, size_t t_i) {
if (t_i == t.size()) return 1;
int sum = 0;
for (int i = s_i; i < s.size(); ++i) {
if (s[i] == t[t_i]) {
if (cache[i + 1][t_i + 1] >= 0) sum += cache[i + 1][t_i + 1];
else sum += work(s, t, i + 1, t_i + 1);
}
}
cache[s_i][t_i] = sum;
return sum;
}由于直接递归会有大量重复计算，同样会超时，这里使用一个简单的优化技巧就是使用缓存，或者叫备忘录，来记录那些已经计算过的值。递归的办法比较容易想到，但效率不高，而且有可能发生栈溢出，这段代码的耗时为 16ms。
思路三
通常这种递归是有可能通过动态规划来解决的，这道题也确实可以通过动态规划解决，那么我们应该怎么使用动态规划来求解这道题呢？首先我们要定义状态，我们可以定义 dp[i][j] 为 s 中前 j 个字符组成的字符串子序列为 t 中前 i 个字符的个数。无论 t[i - 1] 是否等于 s[j - 1]，s 多加上来一个字符是不影响原来的 dp[i][j - 1] 的，而如果加上来这个刚好跟 t 对应的字符相等，就会多出来 dp[i - 1][j - 1] 个子序列，所以我们就可以得到 dp[i][j] = dp[i][j - 1] + t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0 的递推关系。
动态规划还有一个需要思考的地方就是初始条件。很显然，dp[0][·] 也就是 t 为空的时候，子序列的个数永远是 1，而当 t 非空而 s 为空的时候，不可能有子序列。综合初始条件和递推关系，就得到了动态规划版的程序：
int numDistinctDP(string S, string T) {
int dp[T.size() + 1][S.size() + 1];
for (int i = 0; i <= S.size(); ++i)
dp[0][i] = 1;
for (int i = 1; i <= T.size(); ++i)
dp[i][0] = 0;
for (int i = 1; i <= T.size(); ++i)
for (int j = 1; j <= S.size(); ++j)
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * (S[j - 1] == T[i - 1]);
return dp[T.size()][S.size()];
}动态规划版少了递归时函数调用的开销，而且程序也更简洁了，运行时间为 4ms，速度提升了四倍，时间复杂度和空间复杂度都为 $O(S T)$。
思路三优化
思路三中空间复杂度还可以进一步优化，可以看出来，递推时我们只用到了 s 的上一个字符时的状态，我们可以压缩空间，只存储关于 t 的状态。这里采用的是类似于 01 背包问题 的一维数组优化技巧。需要注意的是，因为我们需要上一状态的的前一个字符的信息，所以在循环的时候必须倒着循环，否则就破坏了状态。空间优化过的代码如下：
int numDistinct(string S, string T) {
int dp[T.size() + 1] = {1};
for (int i = 1; i <= S.size(); ++i)
for (int j = T.size(); j > 0; --j)
dp[j] += T[j - 1] == S[i - 1] ? dp[j - 1] : 0;
return dp[T.size()];
}虽然运行时间没有变化，但是空间复杂度降到了 $O(T)$，程序也更加简洁了。