题目：
Given a string S and a string T, count the number of distinct subsequences of T in S. 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). Here is an example: S = "rabbbit", T = "rabbit" Return 3.
解读一下：就是在S是子序列中有多少个和T相同
思路：DP
dp[i][j]表示S前i个字符的子序列和T前j个字符相同的个数。所以，最终返回dp[S.length()][T.length()]
状态转移方程：
如果S[i] T[j]不相等：dp[i+1][j+1] = dp[i][j+1]。 S的第i+1个字符串与T第j+1个不相等，所以不能2个char不能对应，所以S的第i+1个char可以不考虑，dp[i+1][j+1]的结果就是S前i个和T匹配的结果即dp[i][j+1]
如果S[i] T[j]相等：dp[i+1][j+1]=dp[i][j]+dp[i][j+1]。此时分为2中情况，因为末尾两个char相等，所以，如果最后2个char对应匹配，则结果为S前i和T前j的结果；如果末尾两个不做匹配，那么结果是S前i和T前j+1。
代码：
public class Distinct_Subsequences { public int numDistinct(String s, String t) { if(t.length()>s.length()) return 0; if(s.equals(t)) return 1; //dp[i][j]表示s前i个 和 t前j个 匹配上的个数 int dp[][] = new int [s.length()+1][t.length()+1]; //init dp[][] for(int i=0;i<=s.length();i++) dp[i][0]=1; //start dp for(int j=0; j<t.length(); j++){ for(int i=0; i<s.length(); i++){ if(s.charAt(i)==t.charAt(j)) dp[i+1][j+1]=dp[i][j]+dp[i][j+1]; else dp[i+1][j+1]=dp[i][j+1]; } } return dp[s.length()][t.length()]; } }