1st, dp[j] represent number of distinct sequences from an empty string s equals any string with length j, then dp[j] = 0 for all j
2nd, dp[i] represent number of distinct sequences from any string with length i equals an empty string t = "", and such distinct sequence exists and only can be an empty string "", so dp[i] = 1
very excellent solution!!!
but I would like to know how you came out with this solution. When you read this problem, how do you analyze, please kindly help me, because when I met this question, I get totally confused...
What trips people up here (me included) is that the problem does not mean "subsequences of T", it means "subsequences consisting of T". Then, the following words "in S" signify "subsequences of S".
So the problem is: "Count the number of distinct subsequences consisting of T in S" - i.e. "Count the number of distinct subsequences of S that consist of T", or "are equal to T", as noted by vivek.bits.
Even then, it is incorrect. These are not distinct subsequences, as they are all equal. They are distinct ways of forming the same subsequence.
It took me a while to understand how this works. Note that this solution iterates columns first, instead of rows first as in the original easy-to-understand solution. When you iterate column first, the new value in each array element is dependent on the old values of this element and its previous element. That's why you need to iterate from the end.