---
# System prepended metadata

title: LC 115. Distinct Subsequences
tags: [leedcode, DP, LCS, hard, python, c++]

---

# LC 115. Distinct Subsequences

### [Problem link](https://leetcode.com/problems/distinct-subsequences/)

###### tags: `leedcode` `python` `c++` `hard` `DP` `LCS`

Given two strings <code>s</code> and <code>t</code>, return the number of distinct **subsequences**  of <code>s</code> which equals <code>t</code>.

The test cases are generated so that the answer fits on a 32-bit signed integer.

 **Constraints:** 

- <code>1 <= s.length, t.length <= 1000</code>
- <code>s</code> and <code>t</code> consist of English letters.

## Solution 1 - DP
#### Python
```python=
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        # dp[i][j] = number of distinct subsequence of s[:i] which equal t[:j]

        for i in range(1, m + 1):
            dp[i][0] = 1  # s非空, t為空, 所以有1種方法
        for j in range(1, n + 1):
            dp[0][j] = 0  # s為空, t非空, 所以有0種方法
        dp[0][0] = 1  # s為空, t為空, 總共1種方法

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[-1][-1]
```
#### C++
```cpp=
class Solution {
public:
    int numDistinct(string s, string t) {
        typedef unsigned long long int LL;
        vector<vector<LL>> dp(s.size() + 1, vector<LL>(t.size() + 1, 0));
        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < t.size(); j++) {
                if (s[i] == t[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                } else {
                    dp[i + 1][j + 1] = dp[i][j + 1];
                }
            }
        }
        return int(dp.back().back());
    }
};
```

>### Complexity
>m = s.length
>n = t.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(mn)           | O(mn)            |

## Note
sol1:
![image](https://hackmd.io/_uploads/S1OaY3dVC.png)
```cpp=
if (s[i] == t[j]) {
    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
取s[i]和不取s[i]兩種
```
```cpp=
else {
    dp[i + 1][j + 1] = dp[i][j + 1];
}
取dp[i][j + 1]而不是取dp[i + 1][j]是因為t中每個字母皆為必要
```
