动态规划---不同的子序列
题目：给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
例如，s='rabbbit',t='rabbit',结果为3（rabbbit,rabbbit,rabbbit）
思路：
1.确定dp数组及含义
dp[i][j]代表以下标i-1结尾的s子序列中出现以下标j-1结尾的字符串t的个数
2.确定递推公式
如果s[i-1]=t[j-1]，那么可以用s[i-1]匹配，个数为dp[i-1][j-1]；可以不用s[i-1]来匹配,个数为dp[i-1][j]
如果s[i-1]!=t[j-1]，那么个数为dp[i-1][j]
3.初始化dp数组
根据递推公式，我们需要初始化dp[i][0],含义是以下标i-1结尾的s子序列随便删除元素出现空字符串的个数，即个数为1（全删），初始化dp[0][j]，含义是空字符串s随便删除元素出现字符串t的个数，即个数为0
4.确定遍历顺序
从小到大，从左到右遍历
代码：
public int numDistinct(String s, String t) {int len1=s.length();int len2=t.length();int[][] dp=new int[len1+1][len2+1];for(int i=0;i<len1;i++){dp[i][0]=1;}for(int i=1;i<=len1;i++){char c1=s.charAt(i-1);for(int j=1;j<=len2;j++){char c2=t.charAt(j-1);if(c1==c2) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];else dp[i][j]=dp[i-1][j];}}return dp[len1][len2];}