# C++ less than 10 lines dp solution with explanation

• This is similar to Edit Distance problem we solved before, which also needs to build dp array, however, here, from s to t, we can only perform delete operation.

dp array: `dp[i][j]` means the number of distinct subsequences of `t.substr(0, i)` in `s.substr(0,j)`. if `i = 0`, `t.substr(0,0) = ""`, we can say there are 1 instance of that for "". So, initialize `dp[0][j] = 1`, and other `dp[i][j] = 0`.

dp[1][1]: how many A in "A"? It's obvious, dp[1][1] = 1;

dp[1][2]: how many A in "AE"? It's obvious, dp[1][2] = dp[1][1] = 1;

dp[1][3]: how many A in "AECD"? similarly, dp[1][3] = dp[1][2];

... ...

dp[2][6]: how many "AE" in "AECDEE"? Since the end of "AECDEE" matches end of "AE", consider the purpose we build dp, we want to use the result we already calculated, so we can split this into two subproblems:

1. if 'E' in "A`E`" comes from last 'E' in "AECDE`E`"

here, we can then disregard the last 'E' in both sub-string, the answer for this subproblem should be equivalent to calc `dp[i - 1][j - 1]`: how many "A" in "AECDE"?

1. if 'E' in "AE" comes from "A`E`CD`E`"

here, the answer for this subproblem should be equivalent to calc `dp[i][j - 1]`: how many "AE" in "AECDE"?

``````dp[2][6] = dp[1][5] + dp[2][5] = 1 + 2 = 3
``````

Based on above scenarios, we get the following generalized rules

``````if t[i - 1] == s[j - 1] dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
else dp[i][j] = dp[i][j - 1]
``````

Build dp array

``````         A E C D E E C E
0 1 2 3 4 5 6 7 8

0   1 1 1 1 1 1 1 1 1

A 1   0 1 1 1 1 1 1 1 1
E 2   0 0 1 1 1 2
C 3
``````

Final table

``````         A E C D E E C E
0 1 2 3 4 5 6 7 8

0   1 1 1 1 1 1 1 1 1

A 1   0 1 1 1 1 1 1 1 1
E 2   0 0 1 1 1 2 3 3 4
C 3   0 0 0 1 1 1 1 4 4
``````

Code

``````class Solution {
public:
int numDistinct(string s, string t) {
int m = t.size(), n = s.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

for(int i = 0; i <= m; i++){
for(int j = 0; j <= n; j++){
if(i == 0) dp[0][j] = 1;
else{
dp[i][j] = (t[i - 1] == s[j - 1]) * dp[i - 1][j - 1] + dp[i][j - 1];
}
}
}

return dp[m][n];
}
};``````

• Nice explanation. Still one problem : your code can be ACed in OJ, but running in IDE I got exception thrown because s[j-1] would be s[-1] when j==0 within the loop. Strange it didn't cause any error in OJ.

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