Distinct Subsequences
Total Accepted: 15484 Total Submissions: 62324My Submissions
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.
题意：如果某一个字符串str1是由另一个字符串str2中删除某些字符并保持其它字符在str2中的顺序得到的，
那么str1称为str2的子串
思路：
跟 Edit Distance 那道题类似
设 dp[i][j]表示 str1[0...j] 在 str2[0...i]中出现的次数，则
dp[i][j] = dp[i - 1][j] , if str1[j] != str2[i]
因为str1[j] != str2[i]，所以只能删除掉str2[i]
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j], if str1[j] == str2[i]
因为str1[j] == str2[i]，所以可以选择保留 str2[i] 或删除掉它
实现的时候，可以只用一个一维滚动数组 dp[j] --> 只要哪一维在计算 i状态时只用到了 i-1的状态，就可以用滚动数组
-->这里好像错了，这里初始化的时候要将每个 dp[i][0] 设为1，但如果只用一个一维数组的话，就只能将 dp[0][0] 设为1
-->所以还是用二维数组
-->网上看到有人用一维数组也可以，是在 j 循环时，从后往前迭代。
复杂度：时间O(n^2)，空间O(n^2)
int numDistinct(string S, string T) {
vector
> dp(S.size() + 1, vector
(T.size() + 1, 0)); for(int i = 0; i <= S.size(); ++i) dp[i][0] = 1; for(int i = 1; i <= S.size(); ++i){ for(int j = 1; j <= T.size(); ++j){ if(S[i - 1] == T[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; else dp[i][j] = dp[i - 1][j]; } } return dp[S.size()][T.size()]; }