# leetcode: Distinct Subsequences

#### Problem Description:

Given a string **S** and a string **T**, count the number of distinct subsequences of **T** in **S**.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `"ACE"`

is a subsequence of `"ABCDE"`

while `"AEC"`

is not).

Here is an example:

**S** = `"rabbbit"`

, **T** = `"rabbit"`

Return `3`

.

####
Solution and **Precautions**:

DP: let F(i, j) denote the number of ways for S[0]…S[i] contain T[0]..T[j], Then F(n-1, m-1) is our answer and we have

if(S[i] != T[j]) F(i, j) = F(i-1, j);

if(S[i] == T[j]) F(i, j) = F(i-1, j-1) + F(i-1, j);

#### Tips and Divergent thinking:

Be careful on the base case, and for the above recursive definition, recursive implementation might be easier to maintain than for loops.