# DP solution, simple C++ code, and the scroll array optimization with clear explaination

• We define dp[i, j] as the number of subsequence with the first i elements in S, and the jth element as tail in T.
dp[i, j] = dp[i - 1, j] if(S[i] != T[j])
dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1] if(S[i] == T[j])

So we can get the code

``````class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<int> row(m + 1, 0);
vector<vector<int> > dp(n + 1, row);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i-1][j];
if(s[i-1] == t[j-1]) {
dp[i][j] += dp[i-1][j-1];
if(j == 1) dp[i][j]++;
}
}
}
return dp[n][m];
}
};
``````

However, we can find dp[i, j] depends on dp[i - 1, j] and dp[i - 1, j - 1], if we can compute the dp[i - 1, j] and dp[i - 1, j - 1] before dp[i, j], we only need one dimension array. If we draw 2D array, the ascending order i and descending order j are the one of the correct choices. We call this method as the scroll array.

``````class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<int> dp(m + 1, 0);
for(int i = 1; i <= n; i++){
for(int j = m; j >= 1; j--){
if(s[i-1] == t[j-1]) {
dp[j] += dp[j-1];
if(j == 1) dp[j]++;
}
}
}
return dp[m];
}
};
``````

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