LeetCode Q115 Distinct Subsequences (hard)

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:
Finally, I thoroughly solved a DP totally by myself. 

Usually, the question about two strings like this should be solved by DP using a M x N table with time complexity equals O(MN).

Let's have a table H to save all intermediate results. Entry H[i][j] represents the number of distinct subsequences  between S[0:i] and T[0:j].

Following is the transition equation:

i. If S[i]!=T[j], then H[i][j]=H[i-1][j].

ii. If S[i]==T[j], then H[i][j]=H[i-1][j-1]+H[i-1][j].

So, to solve H[i][j], we basically, need to get last row and previous column solved first, which in our problem can be do by two loops and solved rows by rows.