```
public int numDistinct(String s, String t) {
int[] dp = new int[t.length()];
for(int i=0; i<s.length(); i++)
for(int j=t.length()-1; j>=0; j--)
if(s.charAt(i) == t.charAt(j))
dp[j] = ( j==0 ? 1 : dp[j-1]) + dp[j];
return dp[t.length()-1];
}
```

define dp[i][j] as total distinct strings [0,j] of T in [0,i] of S,

then there are two cases:

**dp[i][j] = dp[i-1][j]**,which means we can find [0,j] in [0,i-1].**dp[i][j] = dp[i-1][j] + dp[i-1][j-1]**if**T[j] = S[i]**, either we can find [0,j] in [0,i-1], or find [0,j-1] in [0,i-1] with T[i] = S[i].

with optimization, use one dimension and iterate back forward then

- dp[i] = dp[i]
- dp[i] = dp[i] + dp[i-1]