# 115. Distinct Subsequences

[Link](https://leetcode.com/problems/distinct-subsequences/description/)

Given a string **S** and a string **T**, count the number of distinct subsequences of **S** which equals **T**.

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).

**Example 1:**

```
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
```

**Example 2:**

```
Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^
```

**Solution**

很神奇的使用DP，

建立二微陣列dp\[]\[], 其中dp\[i]\[j] 表示**s取前面i個** 跟**t取前面j個**，能夠形成等於t的組合數, \
i介於(0 到 s.length())\
j介於(0 到 t.length())\
所以:&#x20;

```
int[][] dp = new int[s.length()+1][t.length()+1];
```

其中若i = 0，表示s為空字串，那必定沒可能有組合數。 dp\[0]\[j] = 0 , for all j&#x20;

其中若j = 0，表示t為空字串，那必定組合數都有一個。 dp\[i]\[0] = 1 , for all i\
\
dp\[0]\[0] = 1，都是s, t空字串，組合數為1

```
        for(int j = 0; j< t.length()+1; j++){
            dp[0][j] = 0; //s is empty string
        }
        for(int i = 0; i < s.length()+1; i++){
            dp[i][0] = 1; //t is empty string
        }
```

接下來要推廣dp\[i]\[j]的值\
先考慮s.charAt(i) != t.charAt(j)的狀況，表示s新進的元素，不可能形成組合數，那麼有沒有放入s\[i]都是一樣的。所以此狀況下組和數等於dp\[i-1]\[j]\
反之，若是相等，那接下來就會有兩種可能，一種是仍無法形成組合數 dp\[i-1]\[j]\
另一種為行程組合數，此時組合數的個數會跟s, t各少掉一個元素是一樣的: dp\[i-1]\[j-1]

最後算出dp\[s.length]\[t.length]即為解

```
 public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length()+1][t.length()+1];
        for(int i = 0; i< t.length()+1; i++){
            dp[0][i] = 0; //s is empty string
        }
        for(int j = 0; j < s.length()+1; j++){
            dp[j][0] = 1; //t is empty string
        }
        
        for(int i = 1; i < s.length()+1; i++){
            for(int j = 1; j < t.length()+1; j++){
                if(t.charAt(j-1) == s.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];  
                    // two case: 
                    // 1. have a match : dp[i-1][j-1]
                    // 2. without a match : dp[i-1][j]
                }
                else{
                    dp[i][j] = dp[i-1][j]; // will same as exlude the s.charAt[i]
                }
            }
        }
        
        return dp[s.length()][t.length()];
    }
```
