Dynamic programming (DP) is a group of very useful algorithms to solve searching problems. In many cases, it is easy to realize that a particular problem can be solved in DP, but you may spend a lot of time on finding the iterative equations. Distinct Subsequences is one such problem.
Here is the description from leetcode.
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.
If you are sensitive enough, "two strings" and "subsequence" will guide you to DP immediately. From some previous experience like Edit Distance, you know it is a good idea to construct an m by n matrix, where m = T.length() and n = S.length(). Each element in the matrix, say matrix[i][j], represents the number of distinct subsequences of string T[0:i+1] and S[0:j+1]. Now comes the hard part: how to fill in the matrix?
The matrix can be filled row by row, i.e. each time we add a single character in T and evaluate the number of distinct subsequences for all prefix of S. If T[i] != S[j], since T[0:i+1] is a subsequence of S[0:j+1] (if exists), the new character T[i] should be matched before S[j]. As a result we have the equation matrix[i][j] = matrix[i][j-1].
If T[i] == S[j], there are two possible cases: (1) T[i] is the character that matches to S[j], so we should throw away both T[i] and S[j], and the number of subsequences should equal to matrix[i-1][j-1]; or (2) T[i] is matched to a character before S[j], where we can get the number from matrix[i][j-1], as we have illustrated before. The total number of distinct subsequences is the sum of those two cases, so the equation should be matrix[i][j] = matrix[i-1][j-1] + matrix[i][j-1].
To summarize, the core logic of this DP problem is shown in the following code block
1 | if (S[j] != T[i]) |
Since we only use two adjacent rows in the matrix at any time, the memory consumption can be cut down to $O(n)$ instead of $O(mn)$.
In conclusion, the difficulty of this common DP problem stands on finding the correct iterative equations. Some patterns are well-known for similar problems, such as the allocation of m by n matrix. However you will need to try hard to understand the exact meaning of a cell, and how to connect the meaning among multiple cells.