# Distinct Subsequences

hard | Accept. 50% | 力扣中文站

Given two strings `s`

and `t`

, return *the number of distinct subsequences* of `s`

which equals `t`

.

Example:

```
Input: s = "babgbag", t = "bag"
Output: 5
```

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

## Code

```
// s: babgbag -> iterated by pointer j
// t: bag -> iterated by pointer i
public int numDistinct(String s, String t) {
int S = s.length(), T = t.length();
int[][] dp = new int[T + 1][S + 1];
for (int j = 0; j <= S; j++) {
dp[0][j] = 1; }
for (int i = 1; i <= T; i++) {
for (int j = 1; j <= S; j++) {
if (s.charAt(j - 1) == t.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; } else {
dp[i][j] = dp[i][j - 1]; }
}
}
return dp[S][T];
}
```

## State transition

Fill in the DP table *row by row*. When dealing with a row,
assume `t`

(the shorter string) is *fixed* and `s`

is increasing in character.

Try clicking on different values to show how they are calculated.

"" | b | a | b | g | b | a | g | |
---|---|---|---|---|---|---|---|---|

"" | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

b | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |

a | 0 | 0 | 1 | 1 | 1 | 1 | 4 | 4 |

g | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 5 |