# 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

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++

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:

if (s[i] == t[j]) {
    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
取s[i]和不取s[i]兩種

else {
    dp[i + 1][j + 1] = dp[i][j + 1];
}
取dp[i][j + 1]而不是取dp[i + 1][j]是因為t中每個字母皆為必要