ven a string S and s string T, count the number of distinct subsequences of T in S
这句话的实质是，统计 T 有多少个与 S 一样的子串。结合例子：
S = "rabbbit", T = "rabbit"
^^^
将三个 b 任意删除一个，即可以称为一个独立的子串，并皆与 T 相同。故其结果为 3.
说白了，这道题是问我们有几种选择，譬如例子中，是删除第一个 b, 还是第二个？第三个？。这让我们立刻可以回想起几天前做的一道题：[88. Edit Distance](../88. Edit Distance)，在那道题里，我们也是面对选择，是增加？删除？还是替换？
类似这种多少种情况？多少种选择？ 的问题，我们就需要了解一下，这个问题是否可以分解成重叠的子问题，譬如说这道题，长度为 i 的 S, 长度为 j 的 T, 求有多少种 num(i, j) 解决方案，让 S -> T. 那么其子问题是什么？
很简单，让我求的是长度为 i 和 j, 那我看看 i-1 或 j-1 的情况，看看有没有重叠性？
为了说明的更加具体，我们用实例来分析：
S: rab
T: rabbit
如果 T 比 S 还长，这 T 便显然不是 S 的子串，故 if(i < j) sum(i,j) = 0
那反过来呢？直接让 T 小得可怜：
S: rabbbit
T: (null)
即 T 为空的情况，那么其子串也只有一种可能了，故 sum(i,0) = 1
上面两种极端情况分析过后，再来看几种正常情况：
rabbbits rabbbit
^ ^
S[i] ==> S[i-1]
rabbit rabbit
^ ^
T[j] T[j]
if(S[i] != T[j]) sum(i,j) = sum(i-1, j) 当 S 的末尾字符与 T 的末尾字符不同时，其结果与"去掉该字符无异”，这个自己非常显然了。
那如果相同呢？
rabbbit rabbbi
^ ^
S[i] ==> S[i-1]
rabbit rabbi
^ ^
T[j] T[j-1]
难道是这样的吗？如果相同，也无异？这让人有点怀疑，直接快进到关键的戏份呢？
rabbb rabb
^ ^
S[i] ==> S[i-1]
rabb rab
^ ^
T[j] T[j-1]
(sum(i,j) == 3) (sum(i,j) == 2)
看来明显不成立嘛，莫名其妙的解就少了一个。我们冷静一下，看看这个戏份到底有何不同之处，使我们上面的假设立刻失效。很快，就发现了一个诡异之处，即 S 如果去掉末尾的字符，竟然直接等于 T. 所以当我们将两者末尾的字符都去掉的时候，也同时去掉了一种情况！
加上这种情况，可以为我们组成最后一个公式：
if(S[i] == T[j]) sum(i,j) = sum(i-1,j-1) + sum(i-1, j)
// ^
// 如果去掉 S 的最后一个元素
总结一下这个问题的公式：
___ 0
|true
i < j ? - ____ 1 ____ sum(i-1, j)
|___|j==0 |false
|____ S[i] == T[j] ? -
|____ sum(i-1, j) + sum(i-1,j-1)DP 的问题最终都可以通过一个矩阵来表示解空间，此题也不外如是。此时我们有两个选择：
- 按照上面的逻辑，i 为行，j 为列。外循环为迭代 S, 内循环为迭代 T.
- 反其道而行之，j 为行，i 为列。外循环为迭代 T, 内循环为迭代 S.
若我们笃定存储整个矩阵，那么时间复杂度无区别，皆为 m*n. 时间复杂度也一致。但如果我们仅仅保留当前行的数据，因为 n < m, 所以选择 n 为空间复杂度，更为明智。即选择 1.
为了让大家理解整个矩阵的构成，对于上述两种选择，我都将矩阵列了出来，有识之士可以自己推演一下（都是针对例子：rabbbit 和 rabbit, x 代表 invalid, 即 S 或 T 为空时）
方案1:
j| x 0 1 2 3 4 5
------------------
x| 1 0 0 0 0 0 0 (null vs range rabbit)
i=0| 1 1 0 0 0 0 0 (r vs range rabbit)
i=1| 1 1 1 0 0 0 0 (ra vs range rabbit)
i=2| 1 1 1 1 0 0 0 (rab vs range rabbit)
i=3| 1 1 1 2 1 0 0 (rabb vs range rabbit)
i=4| 1 1 1 3 3 0 0 (rabbb vs range rabbit)
i=5| 1 1 1 3 3 3 0 (rabbbi vs range rabbit)
i=6| 1 1 1 3 3 3 3 (rabbbit vs range rabbit)
方案2:
i| x 0 1 2 3 4 5 6
--------------------
x| 1 1 1 1 1 1 1 1 (range rabbbit vs null)
j=0| 0 1 1 1 1 1 1 1 (range rabbbit vs r)
j=1| 0 0 1 1 1 1 1 1 (range rabbbit vs ra)
j=2| 0 0 0 1 2 3 3 3 (range rabbbit vs rab)
j=3| 0 0 0 0 1 3 3 3 (range rabbbit vs rabb)
j=4| 0 0 0 0 0 0 3 3 (range rabbbit vs rabbi)
j=5| 0 0 0 0 0 0 0 3 (range rabbbit vs rabbit)
这里，我还是按照咱们一致分析的思路选择了方案1，见到讨论里也有很多人选择方案2的。
无论选择哪种，都不太建议选择存储整个矩阵。因为在这道题里完全没有必要。