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.

这个题很容易看出是用 dp,但是 dp 的状态转移方程比较难写出来,就算给出了方程,要去理解我也觉得不是那么容易。而且在网上我也没看到讲的清楚的解释,所以我在理解之后做一下记录,尽量明白地解释一下。

首先我们从例子中找找规律,要找 S 中有多少个不同的 T 这样的子串,这里的不一样是指这个子串在 S中的索引序列不一样。比如S[0,1,2,3,5,6]S[0,1,2,4,5,6]就算不同的子串。那这里面的子问题很容易看出来是,T[0..i-1]表示 T 字符串中0到 i-1 的子串,S[0..j-1]表示 S 字符串中0到 j-1 的子串。那 S[0..j-1]中有多少个 T[0..i-1]这样的子串。那很自然我们用一个二维数组 dp[i][j]表示前面这样一个子问题的解。因为在 dp 表格中 S 和 T 的索引是从1开始,所以我在前面分别用了 i-1j-1。我们先画出这个例子的表格看看:

r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 1 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3

然后我们通过表格中的数字找找规律,S 和 T 前面分别有一列和一行表示 S 和 T 是空字符串。如果 S 为空串,那么T 中不管从0到几的子串都不会出现在 S 中,所以第一列除了dp[0][0] 都为0。如果 T 为空串,因为空串是任何字符串的子串,不管 S 从0到几都包含一个不同的子串 T,所以表格第一行都是1,包括 dp[0][0],因为空串也是空串的子串。

我们先来看表格中那个红色标出的1,这是S[0..j-1]T[0..i-1]最后一个字符不相同的情况。这时候应该和它左边的数字相同,也就是 dp[i][j - 1], 这个什么意思呢?就是说,保持 T[0..i-1]不动,S[0..j-1]往后扩展一个字符,如果这个字符和 T[i-1]不同,那T[0..i-1]S[0..j-1]中出现的次数和T[0..i-1]S[0..j-2]中出现的次数相同。也就是dp[i][j] = dp[i][j - 1]

我们再来看表格中红色标出的那个2。这时 T[i-1] == S[j-1],也就是 S[0..j-1]T[0..i-1]的最后一个字符相同,这时候 dp[i][j]应该等于多少呢。这可以分两种情况,对于 S[0..j-1]中最后那个 b 可以有两种对待方法,用和不用。如果不用的话,那匹配的数量就和上面一样是dp[i][j - 1]。如果用,那就让它匹配 T[0..i-1]的最后一个字符,那匹配的数量就是dp[i-1][j - 1]。而且两种情况没有重复,因为一个用S[0..j-1]的最后那个b,一个不用。

这样状态转移方程就出来了:

方程出来后,代码就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int numDistinct(string S, string T) {
int dp[T.length() + 1][S.length() + 1];
for(int i = 0; i <= T.length(); i++) {
for(int j = 0; j <= S.length(); j++) {
if(i == 0) dp[i][j] = 1;
else if(j == 0) dp[i][j] = 0;
else {
if(T[i - 1] == S[j - 1]) dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
else dp[i][j] = dp[i][j - 1];
}
}
}

return dp[T.length()][S.length()];
}
};