[How to from Error to AC to Better]thoughts and extensions with C++ implementation

• At my first analysis I think about to use the

`````` dp[i][j] : refers the count of the  T[0..j-1]  happens in the S[0...i-1]
``````

So the condition is like this

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

else         dp[i][j] = dp[i-1][j]
``````

But of course this is wrong as the count never add new number.

So where happens wrong ?

Using the tail DP idea, I know it is that we use the bool DP equation but not the count DP equation.

When s[i-1]==t[j-1] , we can also use dp[i-1][j] to count the case we not use the tail element.

So the right equation should be like this:

``````    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]
``````

AC code implementation

``````  class Solution {
public:
int numDistinct(string s, string t) {
int ss=s.size(), tt=t.size();
/** dp[i][j] means t[0..j-1] appears in s[0...i-1] for ** times.
*  if s[i-1]==t[j-1]
*     dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
*  else
*     dp[i][j] = dp[i-1][j]
**/
vector<vector<int>> dp(ss+1, vector<int>(tt+1, 0));
for(int i=0; i<=ss; i++){
for(int j=0; j<=tt; j++){
if(i==0 && j==0) dp[i][j]=1;
else if(i==0)  dp[i][j]=0;
else if(j==0)  dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+(s[i-1]==t[j-1] ? dp[i-1][j-1]:0);
}
}
return dp[ss][tt];
}
};
``````

Here is the compressed DP version using rolling array.

``````class Solution {
public:
int numDistinct(string s, string t) {
int ss=s.size(), tt=t.size();
/** dp[i][j] means t[0..j-1] appears in s[0...i-1] for ** times.
*  if s[i-1]==t[j-1]
*     dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
*  else
*     dp[i][j] = dp[i-1][j]
**/
vector<vector<int>> dp(2, vector<int>(tt+1, 0));
for(int i=0; i<=ss; i++){
for(int j=0; j<=tt; j++){
if(i==0 && j==0) dp[i&1][j]=1;
else if(i==0)  dp[i&1][j]=0;
else if(j==0)  dp[i&1][j]=1;
else dp[i&1][j]=dp[(i-1)&1][j]+(s[i-1]==t[j-1] ? dp[(i-1)&1][j-1]:0);
}
}
return dp[ss&1][tt];
}
};``````

• When I first implement this, I made an error at that I create the array of wrong size ...........

I should create size of (size_s+1) * (size_t+1)

Because the dp[0][I] : means nothing match one char ...

So the DP array dimention should be one bigger than the original data array ...

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

• ``````class Solution {
public:
int numDistinct(string s, string t) {
if(s.size() < t.size() || s.empty() && !t.empty())
return 0;
if(t.empty())
return 1;

vector<vector<int>> f(s.size()+1,vector<int>(t.size()+1,0));
f[0][0] = 1;

for(int i = 0; i <= s.size(); i++)
f[i][0] = 1;

for(int i = 1; i <= s.size(); i++){
for(int j = 1; j <= t.size(); j++){
if(j > i) break;
if(s[i-1] != t[j-1])
f[i][j] = f[i-1][j];
else
f[i][j] = f[i-1][j-1] + f[i-1][j];
}
}

return f[s.size()][t.size()];
}
};
``````

at first I wrote if(s[i-1] != s[j-1]) and I was confused because it actually passed many tests and seemed like a legit program that had some corner cases, but it was actually just a typo

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