preface
It’s time for dynamic programming again, and today I’m going to give you a taste of the horrors of dynamic programming. As soon as I got out of it, I couldn’t wait to share it with you. I don’t want to lose my hair for nothing. Without further ado, to the point!
But before we do that, we have to look at our tetralogy of dynamic programming
Dynamic tetralogy
1. Make suredpIs the state of: defined as one dimensional two dimensional or three dimensional? What does it mean?
2. Determine the state transition equation
3. Initialization, i.edpThe value of an element that can be retrieved from an array
4. Calculate from the bottom updpAnd get the optimal value (traversal order)
Different subsequences
The title
Given a string s and a string t, count the number of occurrences of t in a subsequence of S.
A subsequence of strings is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)
The question data ensures that the answers fit into the range of 32-bit signed integers.
Example:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways to get "rabbit" from S. rabbbit rabbbit rabbbitCopy the codeThought analysis
After reading the topic is not feeling oneself have a kind of spring think such as gushing illusion? I feel like I can do it, but my mind is racing and I don’t know where to start? Does it feel like you’ve done your own careful calculations and clever analysis and figured out how to get the right answer by comparing the differences between two strings and then performing a so-called transformation?
Alas, this is all your illusion!!
Xiaobian I started this idea, thought that without dynamic programming can also do, but finally give up, DO not know which big guy can do so, issued algorithm to let me learn, anyway, I can not do it, there is no way, or use dynamic programming.
Determine the DP array
When we look at string problems, we need to think about the fact that dp arrays are defined as one-dimensional arrays, and even if they were solved, they would be complicated or difficult to understand, and this kind of code can be written by big guys. I’m just going to do the lowest possible thing, and I’m going to define dp as a two-dimensional array dp[I][j]. And then we start to focus on solving the problem, and the meaning of this DP array has something to do directly or indirectly with the object that we’re solving the problem with, how else can we go through and get the result, right? We can think of things with our toes, so we’re crazy about what I ‘ ‘J means.
So we slowly concluded that it should be the result of how many kinds of strings t are included in the first I bits of string S and the number of the first J bits of string T. Finally, I adopted the conclusion that the number of T ending with J-1 in the s-subsequence ending with i-1 is dp[I][j]. Because this is really more fragrant, will not let you feel around, more convenient calculation.
Determine the state transition equation
Now we have to get to the heart of it
How do I get the equation of state? We’re going to see how dp[I][j] comes out. At this point, we need to pay attention to the details. Based on past experience, the letter pairing situation is generally considered when the characters I and J refer to are equal or not equal. This kind of experience is the experience of doing questions in the past, so it is important to brush questions.
At this time, we will analyze based on relatively simple examples, of course, also need to include a variety of cases, not a special case
S = rabb and t = rab let’s start with this whole thing, let’s imagine, how many RABs are found in RabB do we really need to do this so-called delete or add operation? Obviously not, just count the species, so let’s start deriving these two cases,
- S [i-1] is equal to t[j-1]
- S [i-1] is not equal to t[j-1]
When s[i-1] is equal to t[j-1], dp[I][j] can be composed of two parts. For example, the current s and t, at this point in time we need to find how many Ra’s are in raB? Since the last digit is equal, then we need to think about whether to use the last digit, and if we match it with s[i-1], which means that the last digit is equal, then we just need to figure out how many Ra’s there are in RAB, because the last digit b is already shared, Then the number is dp[i-1][J-1]; If s[i-1] is not used to match, that is, we need to see how many RABs there are in raB, which is the previous repetition term, then the number is dp[i-1][j].
So when s and t [I – 1] [1], the same dp [I] [j] = dp [I – 1] [1] + dp [I – 1] [j];
Dp [I][j] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I]
So the recursive formula is: dp[I][j] = DP [i-1][J];
Initialize the
To initialize, we need to review the definition of the dp array: the number of t ending in j-1 in an S subsequence ending in i-1 is dp[I][j].
So how do we initialize it? Dp [0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0],dp[0]. This is the same idea, so it should be 1. Dp [0][j] means the number of the first 0 bits of S including the first 0 bits of T, which is obviously -0. Dp [I][0] means the number of the first 0 bits of S including the first 0 bits of T, which is also the same idea. So it’s still one
Traversal sequence
When determining the ergodic order, we need to see how the recursive formula is, dp[I][j] = DP [i-1][j], dp[I][j] = DP [i-1][J-1] + DP [i-1][j], these links are layer upon layer and interrelated, so it is said that the positive order cannot escape.
Specific code
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
for (int i = 0; i < s.size(a); i++) dp[i][0] = 1;
for (int j = 1; j < t.size(a); j++) dp[0][j] = 0;
for (int i = 1; i <= s.size(a); i++) {for (int j = 1; j <= t.size(a); j++) {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]; }}}return dp[s.size()][t.size()]; }};Copy the codeThe code analysis
I -1 is also useful for this, so you can make the array from the index 1, can represent 0, of course, personal habit, just easy to analyze, prevent halo, finally traversal completed, return dp[I][j] can be concluded
conclusion
In fact, dynamic programming is difficult, but also difficult to determine his DP array and DP equation of state, for these dynamic programming problems, in fact, there are routines. We still need to study hard!
I am xiaobai, we study together!