# 115 Distinct Subsequences C++ DP

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:

S = "rabbbit", T = "rabbit"

Return 3.

### Solution

#### DP

Let `dp[n]`

represent the count of prefix `T[0..n]`

seen so far in `S`

Initial: `dp[*] = 0`

Recurrance:

`dp[n]`

depends on `dp[n-1]`

and `dp[n]`

To illustrate consider this example:

`S="RRABAB"`

, `T="RAB"`

initially: `dp = [0, 0, 0] #[R A B]`

Lets iterate over `S`

```
s='R' => dp = [1 0 0]
s='R' => dp = [2 0 0] # We have already seen the prefix 'R' so add one more
s='A' => dp = [2 2 0] # We have seen 2 R's and we see one A so 2 RA's are possible
s='B' => dp = [2 2 2] # 2 RA's seen earlier + B => 2 RAB's
s='A' => dp = [2 4 2] # 2 RA's seen earlier + 2 R's before this A => 4RAs
s='B' => dp = [2 4 6] # 2 RAB's seen earlier + 4 RA's before this B => 6RABs
```

This can be summarised in this relationship for each iteration:

`dp[n] = dp[n] + dp[n-1]`

With repeating characters in `T`

the key is to apply the relationship from the farthest character towards the earlier character.

```
S="RRAABAB"
T="RAAB"
- [0 0 0 0]
R [1 0 0 0]
R [2 0 0 0]
A [2 2 0 0] # 'A' at 2 followed by 'A' at 1
A [2 4 2 0] # 'A' at 2 followed by 'A' at 1
B [2 4 2 2]
A [2 6 6 2] # 'A' at 2 followed by 'A' at 1
B [2 6 6 8]
```

#### C++ Code

```
int numDistinct(string s, string t) {
vector<int> dp(t.size(), 0);
for(auto c: s)
for(auto pos = t.size(); pos and (pos = t.find_last_of(c, pos-1))!=string::npos;)
dp[pos] += pos?dp[pos-1]:1;
return dp[t.size()-1];
}
```