Leetcode之Distinct Subsequences 问题

问题描述：

Given a string S and a string T, count the number of distinct subsequences of S whichequals T.

A subsequence of a string is a new string which is formed from the original string bydeleting some (can be none) of the characterswithout disturbing the relative positions of the remaining characters. (ie,"ACE" is a subsequence of"ABCDE" while "AEC" is not).

示例：

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

问题来源：Distinct Subsequences (详细地址：https://leetcode.com/problems/distinct-subsequences/description/)

思路分析：这道题和Delete Operation for Two Strings 非常的相似，但是也有很大的不同，这道题的意思是只可以用删除字符的方法从第一个字符串变换到第二个字符串，求出一共有多少种变换方法。但是，Delete Operation for Two Strings 考虑的是将S和T中删除最少的字符，使得两个字符串所剩部分是一样的。加而言之，这道题T是固定住的，而另外的那道题是需要考虑两个字符串都要删除的。前面的那道题只需要求出最长公共子序列，然后一减就得到结果了。而这道题需要考虑的就更多一些了。Edit Distance 这道题和本题有点相似，但是本题只允许删除，而Edit Distance 是允许插入.删除和替换的。接下来还是回到这道题，这道题需要采用动态规划来求解。下面详细介绍一下如何解答这道题:

      1）首先我们建立一个二维数组，其中行数为s.length()+1，列数为t.length()+1，接着我们开始初始化工作：假设当T是空字符串的话，对于每个S来讲只有一种办法，就是也将它们都删除，才能变成T，翻译过来就是：dp[i][0] = 1;(因为t此时是空的，所以我们刚开始还没必要判断t为空的情况，是不是在这简化了不少？)；接着，如果S为空字符串呢？那当然是没办法将空字符串通过删除的办法得到非空字符串的啊，所以有0种办法，翻译过来就是：dp[0][j]=0;另外，我们讲一下dp[0][0]=1，从空字符串编程空字符串我们是有一种办法的；

     2.）接着确定状态转移方程：假设分别两个指针指向两个字符串，i指向S，j指向T。每一轮，在这考虑S[0...i]包含T[0...j]的子序列的时候，我们是假设T是固定的，而S是一个一个添加的(最重要的一点！)。假设当前两个指针所指向的字符是不一致的，所以我们向S添加这个字符不添加这个字符是一样的，也就是说当前的办法数是等于添加该字符之前的办法数的，即：dp[i][j] = dp[i - 1][j]；相反的，如果两个字符是一致的，我们可以有两种情况，也就是如果两个字符进行匹配的话，那现在的办法数和分别在两字符串中删除该字符数的结果是一样的，即：dp[i][j] = dp[i - 1][j - 1];而如果不匹配的话，那么它的意思就是我们可以无视当前添加到S中的这个字符，所以它的办法数也是和添加该字符之前的办法数是一样的，即dp[i][j] = dp[i - 1][j]。这两种办法都属于当前字符相等的情况，所以合并起来就是dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]。

下面讲解一个例子：假设S="acdabefbc"，T="ab"，初始化我们的结果就是（为了习惯中国人的审美，我们把S换成横着来了，T竖着来）： 

             a  c  d  a  b  e  f   b  c

    S:  0  1  2  3  4  5  6  7  8  9 

T：0  1  1  1  1  1  1  1  1  1  1

a : 1   0  

ab:2   0

第0行代表的是T为空的情况，第0列代表的是S为空的情况。

       接着我们固定住T，刚开始T="a"；S开始一个一个地添加，第一个a就和T的"a"就是相等的，所以我们可以选择匹配(相当于两个字符都删除a)，办法数=1，也可以选择不匹配，不匹配的话那就相当于这个a是白添加进来的，所以办法数=0，因为现在T为空了，最终更新后，T[1]就变成了下面的情况：

        a : 1(第一行)  0  1  1  1  2  2  2  2  2  2 ，中间突然变成2是因为我们碰到了另外的一个a，我们又可以选择匹配和不匹配的问题了，所以它等于它左上角的数(dp[0][3])加上它左边的这个数(dp[1][3]),即1 + 1 = 2，其他的不相等的情况直接就等于它左边的那个数了；

      接着，我们看看T变成了"ab"，即T固定为了"ab"，现在我们往S中一个一个地添加字符，当前匹配的字符就是尾字符'b'了，因为前面的'a'在上一轮已经讨论过了，同理，我们在S中一个一个的往右匹配，一碰到相等的元素的时候，我们就得讨论匹配和不匹配的问题了，即左上角的数加上左边的数，得到T[2]的情况如下：

      ab:2(第二行) 0  0  0  0  0  2  2  2  4  4.

      所以最后的结果是4，其实这4中情况就是数字突增的这四个位置两两组合起来得到的情况。

代码：

初始化部分：

状态转移部分：