Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences ofT 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.
思路：
如果搜索解空间肯定超时。那么考虑用动态规划填表来做。例如题目中的例子
| T/S | r | a | b | b | b | i | t |
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| ra | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| rab | 0 | 0 | 1 | 2 | 3 | 3 | 3 |
| rabb | 0 | 0 | 0 | 1 | 3 | 3 | 3 |
| rabbi | 0 | 0 | 0 | 0 | 0 | 3 | 3 |
| rabbit | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
：
填充规则是，若S对应字符和T最末字符不同，则取同行前一列的值，因为该字符肯定不选；否则，取同行前一列的值（不选S中此字符）和上一行前一列的值（选S中此字符）。最后最右下表格数值即为总共的可能方法个数。
题解：
class Solution {
public:
int numDistinct(const string& S, const string& T)
{
if (S.size() ==0)
return 0;
// initialize the dynamic programming table, S in column and T in row
vector<vector<int>> acc;
acc.resize(S.size());
for (auto & a : acc)
{
a.resize(T.size());
fill(begin(a), end(a), 0);
}
if (S[0] == T[0]) acc[0][0] = 1;
for (int i = 1; i < S.size(); ++i)
{
char s = S[i];
for (int j = 0; j < T.size(); ++j)
{
char t = T[j];
if (s != t)
acc[i][j] = acc[i - 1][j];
else
acc[i][j] = acc[i - 1][j] + ( j == 0 ? 1 : acc[i - 1][j - 1]);
}
}
return acc[S.size() - 1][T.size() - 1];
}
};