[LeetCode]Distinct Subsequences

对于string S和T，我们要找S中有多少不同的和T一样的subsequence。用DP[i][j]表示T的前i个char和S的前j个char有多少个distinct subsequence，我们可以得到递推方程：

• DP[i][j] = DP[i][j - 1] + DP[i - 1][j - 1], T[i] == S[j]
• DP[i][j] = DP[i][j - 1], T[i] != S[j]

第二个公式比较好理解，如何理解第一个递推公式呢？第一项DP[i][j - 1]代表不考虑S[j]原有的distinct subsequence，第二项DP[i - 1][j - 1]代表我们将T[i]和S[j]match之后，新加上的distinct subsequence。假设T长m，S长m，时间复杂度O(m * n)，空间复杂度O(m * n)，代码如下：

空间可以优化为O(m)，代码如下：