# Leetcode 115 - Distinct subsequences

`Note`

`dp[i][j]`

means the number of distinct sub between`s[0 - i-1]`

that ends with`s[i-1]`

and`t[0 - j-1]`

that ends with`t[j-1]`

.- When
`s[i-1] === t[j-1]`

, two situations to consider:- consider
`s[0 - i-2]`

and`t[0 - j-2]`

. - Don’t consider
`s[i-1]`

, take`s[0 - i-2]`

and`t[0 - j-1]`

into consideration.

- consider
- To initialize:
`dp[0][j] = 0`

because`t`

can’t be subsequence of an empty string.`dp[i][0] = 1`

because empty string is a subsequence of any string.

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 = "babgbag", t = "bag" |

1 | /** |