思路：本题依旧先确定dp数组及其含义，往往题目要求求什么，dp数组的含义就是什么，所以在本题中dp数组含义为 dp[i][j]表示以i-1结尾的s中出现j-1结尾的t的个数。
然后就到了本题的难点，dp数组在遍历中的推导过程，很明显在子序列这一类题目中，我们需要判断s[i-1]和t[j-1]是否相等，相等时很容易想到直接用s[i-1]进行匹配那么我们只需要让dp[i][j]继承 dp[i-1][j-1]的即可 即 dp[i][j] = dp[i-1][j-1]。
而s[i-1]和t[j-1]不相等时，只能用s的上一位进行匹配，则dp[i][j] = dp[i-1][j];
然后会发现一直无法ac
实际上当s[i-1]和t[j-1]相等时应当同时考虑两种情况，用s[i-1]进行匹配或者不用s[i-1]进行匹配而是继承s中上一位的dp值，例如 s= buss t=bus 当s[3]=t[2]时，我们可以用
s中的bus或者bu s进行匹配。那么实际上相等时dp[i][j]的值应当是两种情况之和
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
class Solution {
public int numDistinct(String s, String t) {
if(s.length() < t.length()) return 0;
int[][] dp = new int[s.length()+1][t.length()+1];
// dp[i][j]表示以i-1结尾的s中出现j-1结尾的t的个数
for (int i = 1;i < t.length() + 1;i++){
dp[0][i] = 0;
}
//dp[0][0]为1
for (int i = 0;i < s.length() + 1;i++){
dp[i][0] = 1;
}
for (int i = 1; i < s.length() + 1;i++){
for (int j = 1; j < t.length() + 1 ; j++) {
if (s.charAt(i-1) == t.charAt(j-1)){
// 单个字母相等时要分为两部分 用s[i-1]来匹配和不用s[i-1]来匹配 这里比较难想到
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}else {
// 不相等的时候 只能不用s[i-1]来匹配 直接继承上一位的值
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.length()][t.length()];
}
}
