---
# System prepended metadata

title: 0115. Distinct Subsequences
tags: [Leetcode, Dynamic Programming, Hard]

---

# 0115. Distinct Subsequences
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/distinct-subsequences/
## 思路
```dp[i][j] => s[1:i]```有多少不同的子序列等于```t[1:j]```

依照套路，我们首先分析如果```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
```java=
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];
    }
}
```