# 0115. Distinct Subsequences
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/distinct-subsequences/
## 思路

依照套路，我们首先分析如果```s[i]==t[j]```的情况。显然，这两个字符相等，我们就将注意力前移，集中在```s[1:i-1]```和```t[1:j-1]```上。```dp[i-1][j-1]```表示```s[1:i-1]```中有多少个不同的子序列等于```t[1:j-1]```，两边分别加上```s[i]和t[j]```之后，自然就有相同多数目的```s[1:i]```的不同子序列等于```t[1:j]```。所以算上这部分，```dp[i][j]+=dp[i-1][j-1]```。

如果```s[i]!=t[j]```的话，说明```s[i]```指望不上，我们就将注意力放在```s[1:i-1]```上，看里面有多少个不同子序列等于```t[1:j]```，直接拿过来用就行，反正加上了```s[i]```也不管事。所以这种情况下，```dp[i][j]+=dp[i-1][j]```.

注意：当```s[i]==t[j]```的时候，上述的第二种情况也是要累加进去的。原因也是显然的。

递推关系有了，那么边界条件呢？无非就是```dp[0][j]```和```dp[i][0]```的情况。显然，前者仍算是一种子序列，所以赋值为1，后者赋值为0.
## Code

class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m+1][n+1];
for(int i=0; i<=m; i++){
dp[i][0] = 1;
}

for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s.charAt(i-1)==t.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[m][n];
}
}