115. 不同的子序列

给定一个字符串s和一个字符串t ，计算在s的子序列中t出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。 （例如，”ACE”是”ABCDE”的一个子序列，而”AEC”不是）

输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

思路：

1. dp table 设计

对于这种有两个string的题，一般的想法就是用个二维数组，两个维度分别对应 s 和 t 的字符。这题我们也可以这样，用 dp[][] 数组记录状态。
至于状态 dp[i][j] 是什么，我们可以比较直白地就用 dp[i][j] 表示 s 前 i 个字符中包含 t 的前 j 个字符的子序列个数，即：题目要求的是什么，我们就用 dp 记录什么。

2. 初始化

那么我们该怎么初始化 dp[][] 数组的状态呢？ 对于这一题，我们需要考虑到的是当 s 或 t 为空的时候该怎么处理。
1). 很明显， s 为空的话，如果 t 不为空，那么 s 中 t 出现的个数为 0;
2). 相反，如果 t 为空的话，那么无论 s 是什么，t 总会在 s 中出现刚好 1 次。注意由题意我们知道所谓出现次数，就是从 s 中删除某些字符之后刚好得到 t 的方法个数。 t 为空的话，我们删除 s 中所有字符即可，因此出现次数为 1。

3. 转移方程

接下来的问题就是：我们怎么由子状态得到当前状态？ 对于这个问题，对于 dp[i][j], 即 s 的前 i 个字符 中 t 的前 j 个字符出现的次数，我们需要分下面两种情况讨论：
1). s[i] == t[j]， 即当前字符相等，那么这个时候 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]，加法的两项分别对应着s的子串中 保留s[i] （s[i] 对应 t[j]， 这样的子串个数为 dp[i-1][j-1]） 和 不保留s[i] 两种情况
2). s[i] ！= t[j]，即当前字符不等，那么删除字符后 s[i] 必定不能被保留， 所以 dp[i][j] = dp[i-1][j]， 即: s 的前 i 个字符 中 t 的前 j 个字符出现的次数, 等于 s 的前 i-1 个字符 中 t 的前 j 个字符出现的次数

4. 结果

结果就是 s 的所有字符中包含 t 中所有字符的字串个数，即 dp[m][n]， m，n分别为 s 和 t 的长度。

滚动数组优化空间

观察上面的转移方程，我们发现 dp[i] 的值只跟 dp[i-1] 这一行的值有关，因此，我们可以用滚动数组优化空间，减少一个维度。
注意使用滚动数组的时候内部循环 j 的取值是由大到小的，这是为了避免重复计数而导致错误的结果。

  1. //二维dp，时空都为Omn，字符串匹配问题
  2. func numDistinct(s string, t string) int {
  3.     m, n := len(s), len(t)
  4.     dp := make([][]int, m+1)
  6.     for i := range dp {
  7.         dp[i] = make([]int, n+1)
  8.         dp[i][0] = 1                //t为空时，怎么都已有一个;初始化：对于空的t，计数为1
  9.     }
  11.     //for i := 0; i <= m; i++ {         //等价于range，0~m闭区间；有时会搞不清从1还是0起步
  12.     //    dp[i] = make([]int, n+1)
  13.     //    dp[i][0] = 1
  14.     //}
  16.     for i := 1; i <= m; i++ {
  17.         for j := 1; j <= n; j++ {
  18.             if s[i-1] == t[j-1] {
  19.                 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
  20.             } else {
  21.                 dp[i][j] = dp[i-1][j]
  22.             }
  23.         }
  24.     }
  25.     return dp[m][n]
  26. }
//滚动数组，空间优化Om
func numDistinct(s string, t string) int {
    m, n := len(s), len(t)
    dp := make([]int, n+1)
    dp[0] = 1                               //初始化：对于空的t，计数为1

    for i := 1; i <= m; i++ {
        for j := n; j >= 1 ; j-- {          //为啥要逆序？因为从j-1开始比？避免重复计数而导致错误
            if s[i-1] == t[j-1] {
                dp[j] += dp[j-1]            //p[i] 的值只跟 dp[i-1] 这一行的值有关
            }
        }
    }
    return dp[n]
}