# Easy to understand, Distinct Subsequences DP accepted code

• define numDistinct(S,T) is the number of distinct subsequences of S which equals T. The subsequences must start from certain element of S. Then we have
numDistinct(S,T) = sum{numDistinctStart(S[i:],T)},
where numDistinctStart(S[i:],T) is the number of subsequence starting from index i, which equals string T. We have:
numDistinctStart(S[i:],T[j:]) =0, if S[i]!=T[j]
numDistinctStart(S[i:],T[j:]) = \sum_{k=i+1}^S.size() numDistinctStart(S[k:],T[j+1:]) if S[i]==T[j]

And we have numDistinctStart(S,T)==0 if S.size()<T.size(), numDistinctStart(S[i:],T[j:])=1 if j==T.size() and S[i]== T[T.size()-1]. The following code is accepted. Maybe the code can be optimized.

class Solution {
public:
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
int numDistinct(string &S, string &T) {
vector<vector<int>> numDistinctStart(S.size(), vector<int>(T.size(), 0));
for (int i = numDistinctStart.size() - 1; i >= 0; i--) {//relation
for (int j = numDistinctStart[0].size() - 1; T.size() - j <= S.size() - i&&j>=0; j--) {
if (S[i] == T[j]) {
if (j+1==T.size()) {
numDistinctStart[i][j] += 1;
}
else {
for (int k = i + 1; k < S.size(); k++) {
numDistinctStart[i][j] += numDistinctStart[k][j + 1];
}
}
}
}
}
int result = 0;
for (int i = 0; i < numDistinctStart.size(); i++) {
result += numDistinctStart[i][0];
}
return result;
}
};


Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.