# 0115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences

## Description

Given two strings `s` and `t`, return _the number of distinct subsequences of `s` which equals `t`_.

A string's **subsequence** is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., `"ACE"` is a subsequence of `"ABCDE"` while `"AEC"` is not).

It is guaranteed the answer fits on a 32-bit signed integer.

**Example 1:**

```
**Input:** s = "rabbbit", t = "rabbit"
**Output:** 3
**Explanation:**
As shown below, there are 3 ways you can generate "rabbit" from S.
**rabb**b**it**
**ra**b**bbit**
**rab**b**bit**
```

**Example 2:**

```
**Input:** s = "babgbag", t = "bag"
**Output:** 5
**Explanation:**
As shown below, there are 5 ways you can generate "bag" from S.
**ba**b**g**bag
**ba**bgba**g**
**b**abgb**ag**
ba**b**gb**ag**
babg**bag**
```

**Constraints:**

* `1 <= s.length, t.length <= 1000`
* `s` and `t` consist of English letters.

## ac

```java
class Solution {
    public int numDistinct(String s, String t) {
        // edge cases
        if (s == null || t == null || s.length() < t.length()) return 0;

        int slen = s.length(), tlen = t.length();
        int[][] dp = new int[tlen+1][slen+1];

        // init
        for (int si = 0; si <= slen; si++) {
            dp[0][si] = 1;
        }

        for (int ti = 1; ti < dp.length; ti++) {
            for (int si = 1; si < dp[0].length; si++) {
                if (s.charAt(si-1) == t.charAt(ti-1)) {
                    dp[ti][si] = dp[ti][si-1] + dp[ti-1][si-1];
                } else {
                    dp[ti][si] = dp[ti][si-1];
                }
            }
        }

        return dp[tlen][slen];
    }
}

/*
dp[ti][si], s.substring(0, si) contains #distinct subsequences of t.substring(0, ti)

*/
```
