How does C++ solve the problem of different subsequences

This article mainly explains "how C++ solves different sub-sequence problems". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought. Let's study and learn how C++ solves different sub-sequence problems.

Different subsequences

Example 1:

Input: s =

"rabbbit"

, T =

"rabbit"

Output: 3

Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.

(The caret symbol ^ means the chosen letters)

Rabbbit

^

Rabbbit

^

Rabbbit

^

Example 2:

Input: s =

"babgbag"

, T =

"bag"

Output: 5

Explanation:

As shown below, there are 5 ways you can generate "bag" from S.

(The caret symbol ^ means the chosen letters)

Babgbag

^ ^ ^

Babgbag

^ ^ ^

Babgbag

^ ^ ^

Babgbag

^ ^ ^

Babgbag

^ ^

When you see a problem about a subsequence of a string or a registration class, the first thing you should consider is to use dynamic programming Dynamic Programming to solve it, which should be a conditional reflection. The core of all DP problems is to find out the state transition equation, which is to recurse a two-dimensional dp array, where dp [I] [j] denotes the number of subsequences in substrings whose range is [0, I] in s that can make up substrings in range [0, j] in t. Let's analyze it from the example given in the title. The two-dimensional dp array should be:

Dead r a b b b i t

1 1 1

R 0 1 1 1

A 0 0 1 1 1

B 0 0 0 1 2 3 3 3

B 0 0 0 1 3 3 3

I 0 0 0 3 3

T 0 0 0 3

First, 1 is returned if both the original string and the subsequence are empty, because the empty string is also a subsequence of the empty string. If the original string is not empty and the subsequence is empty, it also returns 1, because the empty string is also a subsequence of any string. When the original string is empty and the subsequence is not empty, 0 is returned, because a non-empty string cannot be a subsequence of an empty string. Sort out these, the edge of the two-dimensional array dp can be initialized, as long as you find the state transition equation, you can update the entire dp array. By observing the two-dimensional array above, we can find that when updating to dp [I] [j], dp [I] [j] > = dp [I] [j-1] is always true. Further observation shows that when T [I-1] = S [j-1], dp [I] [j] = dp [I] [j-1] + dp [I-1] [j-1], if not equal. Dp [I] [j] = dp [I] [j-1], so, to sum up, the recursive formula is:

Dp [I] [j] = dp [I] [j-1] + (T [I-1] = S [j-1]? Dp [I-1] [j-1]: 0)

Based on the above analysis, the code can be written as follows:

Class Solution {public: int numDistinct (string s, string t) {int m = s.size (), n = t.size (); vector dp (n + 1, vector (m + 1)); for (int j = 0; j