Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation: As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters) rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
题意：
给定字符串S和T，求字符串S中有多少种不同的subsequences能完全match字符串T
思路：
这是一道高频dp题，需要熟练掌握
注意区分substring(要求连续)和subsequence(不要求连续)
进一步理解题意，
S ： rabbbit 删掉第一个‘b’ ， 可以跟T完全match
S ： rabbbit 删掉第二个‘b’ ， 可以跟T完全match
S ： rabbbit 删掉第三个‘b’ ， 可以跟T完全match return 3 （number of distinct subsequences）
用dp[i][j]来记录S的子序列跟T匹配的个数
初始化的时候，除了要处理dp[0][0]，还要条件反射的习惯性思考是否需要预处理第一个row : dp[0][j] 和第一个col：dp[i][0]
T = 0 "r a b b i t"
0 1 0 0 0 0 0 0
S = "r 1 1 0 0 0 0 0
a 1 1 1 0 0 0 0
b 1 1 1 1 0 0 0
b 1 1 1 2 1 0 0
b 1 1 1 3 ?
i 1 1
t 1 1
显然，
对于是否需要预处理第一个row : dp[0][j], 发现当S为空，T为任意字符都不可能跟S匹配。 对于dp[0][j]不需要多做处理，只保留defalut值为0即可
对于是否需要预处理第一个col：dp[i][0], 发现当T为空，S的当前字符都可以partition into two subsequences : " " + 当前字符， 所以dp[i][0] = 1
对于dp[i][j]，
若 s.charAt(i-1) ! = t.charAt(j-1) 则S当前的字符必须删掉，再看S和T是否匹配： dp[i][j] = dp[i-1][j]
若 s.charAt(i-1) == t.charAt(j-1) 则S当前的字符要么删掉：dp[i][j] = dp[i-1][j] ； 要么保留：dp[i][j] = dp[i-1][j-1]
代码
class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() +1 ][t.length() + 1];
dp[0][0] = 1;
for(int i = 1; i <= s.length() ; i++){
dp[i][0] = 1;
}
for(int i = 1; i <= s.length() ; i++){
for(int j = 1; j<=t.length(); j++){
if( s.charAt(i-1) != t.charAt(j-1) ){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
}
return dp[s.length()][t.length()];
}
}