不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例1:

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

示例2:

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

思路一:

第一种思路很自然的dfs，也很自然的超时了。。。

class Solution {
    private String s;
    private String t;
    private int num;
    private char[] charS;
    private char[] charT;
    private int sLen;
    private int tLen;
    //s的子序列中找t
    public int numDistinct(String s, String t) {
        this.s=s;
        this.t=t;
        this.charS=s.toCharArray();
        this.charT=t.toCharArray();
        this.tLen=t.length();
        this.sLen=s.length();
        dfs(0,0);
        return num;
    }
    private void dfs(int index,int beginIndex) {
        if(index==tLen||beginIndex==sLen){return;}
        Character character=charT[index];
        for(int i=beginIndex;i<sLen;i++){
            if(character==charS[i]){
                if(index==tLen-1){
                    num++;
                    continue;
                }
                dfs(index+1,i+1);
            }
        }
        return;
    }
}

思路二：

动态规划，实际上在大部分可以使用dfs的问题上，都可以使用dp解决。

1.首先第一步：定义状态
定义 f[i][j]为考虑 s 中 [0,i]个字符和t 中 [0,j]个字符的匹配个数。
2.第二步：状态转移方程
（1）s[i]==t[j]时，f[i][j]=f[i-1][j-1]+f[i-1][j]，我们可以使用s中下标为i的字符去进行匹配，也可以不用它进行匹配。
（2）s[i]!=t[j]时，f[i][j]=f[i-1][j]。
3.第三步：初始条件
我们在s和t的头部都拼接一个“ ”空串，那么显然初始条件f[i][0]=1

代码：

class Solution {
    public int numDistinct(String s, String t) {
        // 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始
        // 同时由于往头部插入相同的（不存在的）字符，不会对结果造成影响，而且可以使得 f[i][0] = 1，可以将 1 这个结果滚动下去
        int n = s.length(), m = t.length();
        s = " " + s;
        t = " " + t;
        char[] cs = s.toCharArray(), ct = t.toCharArray();
        // f(i,j) 代表考虑「s 中的下标为 0~i 字符」和「t 中下标为 0~j 字符」是否匹配
        int[][] f = new int[n + 1][m + 1];
        // 原字符只有小写字符，当往两个字符插入空格之后，f[i][0] = 1 是一个显而易见的初始化条件
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 包含两种决策：
                // 不使用 cs[i] 进行匹配，则有 f[i][j] = f[i - 1][j]
                f[i][j] = f[i - 1][j];
                // 使用 cs[i] 进行匹配，则要求 cs[i] == ct[j]，然后有  f[i][j] += f[i - 1][j - 1]
                if (cs[i] == ct[j]) {
                    f[i][j] += f[i - 1][j - 1];
                } 
            }
        }
        return f[n][m];
    }
}

空间优化代码:

怎么优化？第一次我尝试优化的时候直接将原先二维数组中第一维的都去掉，但是这样子结果是错误的，因为逻辑上不成立了，对于f[i-1][j]，i-1代表的是前一行，我们填表的顺序就是从0开始一行一行的，ok那就没问题。但是对于f[i-1][j-1]来说，要用到的同样是前一行的j-1，那么j就需要从后往前填，这样每次用到的f[j-1]就是前一行的，如果j也是从0开始往后填的话，那么每次使用的f[j-1]实际上是f[i-1][j-1]。


class Solution {
    public int numDistinct(String s, String t) {
        // 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始
        // 同时由于往头部插入相同的（不存在的）字符，不会对结果造成影响，而且可以使得 f[i][0] = 1，可以将 1 这个结果滚动下去
        int n = s.length(), m = t.length();
        s = " " + s;
        t = " " + t;
        char[] cs = s.toCharArray(), ct = t.toCharArray();
        // f(i,j) 代表考虑「s 中的下标为 0~i 字符」和「t 中下标为 0~j 字符」是否匹配
        int[] f = new int[m + 1];
        // 原字符只有小写字符，当往两个字符插入空格之后，f[i][0] = 1 是一个显而易见的初始化条件
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >0; j--) {
                // 包含两种决策：

                // 使用 cs[i] 进行匹配，则要求 cs[i] == ct[j]，然后有  f[i][j] += f[i - 1][j - 1]
                if (cs[i] == ct[j]) {
                    f[j] += f[j - 1];
                } 
            }
        }
        return f[m];
    }
}

leetcode115-不同的子序列