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,
is a subsequence of
Here is an example:
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 = T.length()
n = S.length()
. Each element in the matrix, say
, represents the number of distinct subsequences of string
. 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
and evaluate the number of distinct subsequences for all prefix of
T[i] != S[j]
is a subsequence of
(if exists), the new character
should be matched before
. As a result we have the equation
matrix[i][j] = matrix[i][j-1]
T[i] == S[j]
, there are two possible cases: (1)
is the character that matches to
, so we should throw away both
, and the number of subsequences should equal to
; or (2)
is matched to a character before
, where we can get the number from
, 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
if (S[j] != T[i])
matrix[i][j] = matrix[i][j-1];
matrix[i][j] = matrix[i-1][j-1] + matrix[i][j-1];
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
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.