# 115. Distinct Subsequences

{% hint style="success" %}
Two-sequence DP problem. It's easy to define `distinct[i][j],` which means how many distinct ways from `s[:i] to t[:j]`. But how to compute `distinct[i][j]` according to `distinct[i-1[j], distinct[i][j-1]` and `distinct[i-1][j-1]` is difficult to have an idea.
{% endhint %}

### Solution:

1. Initilize `distinct[i][j]`, set empty row and column. `distinct[0][0]=1`, from `s[i]` to `NULL` is 1, from `NULL` to `t[j]` is 0.
2. If `s[i] = t[j]`, then `distinct[i][j]=distinct[i-1][j-1]+distinct[i-1][j]`, think this with drawing.
3. If `s[i] != t[j]`, then  `distinct[i][j]=distinct[i-1][j-1]`.
4. Return `distinct[len(s)][len(t)]`.

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # distinct[i][j], means how many distinct ways can generate from s[:i] to t[:j]
        # initilize distinct[i][j]
        distinct = [[0]*(len(t)+1) for i in range(len(s)+1)]
        
        distinct[0][0] = 1
        for i in range(1, len(s)+1):
            distinct[i][0] = 1
        for j in range(1, len(t)+1):
            distinct[0][j] = 0
            
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    distinct[i][j] = distinct[i-1][j] + distinct[i-1][j-1]
                else:
                    distinct[i][j] = distinct[i-1][j]

        return distinct[len(s)][len(t)]
```

{% endtab %}

{% tab title="Java" %}

```java
class Solution {
    public int numDistinct(String s, String t) {
        int[][] ways = new int[s.length()+1][t.length()+1];
        for(int i = 0; i <= s.length(); i ++)
            ways[i][0] = 1;
        for(int j = 1; j <= t.length(); j ++)
            ways[0][j] = 0;
        
        for(int i = 1; i <= s.length(); i ++)
            for(int j = 1; j <= t.length(); j ++) {
                if(s.charAt(i-1) == t.charAt(j-1))
                    ways[i][j] = ways[i-1][j] + ways[i-1][j-1];
                else
                    ways[i][j] = ways[i-1][j];
            }
        return ways[s.length()][t.length()];
    }
}
```

{% endtab %}
{% endtabs %}

{% hint style="danger" %}
`distinct[i][j]` 与`distinct[i][j-1]`没有任何关系。

这种题最重要的思维是找二维数组`distinct[i][j]` 与前面的 `distinct[i-1][j], distinct[i][j-1], disintct[i][j]` 中的谁有直接关系，并且有什么逻辑联系。
{% endhint %}