# 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.

（全文完，原创文章，转载时请注明作者和出处）

（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）

Written on June 5, 2013