不同的子序列
给定一个字符串 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];
}
}
