Article directory
- 1. Introduction to the idea of moving rules
- 2. The Nth Tabonacci sequence
- 3. Three-step question
- 4. Climb the stairs with minimal cost
- 5. Decoding method
- 6. Summary of dynamic rule analysis
For each algorithm, it is best to read the first article before looking for the blog you want to read, because this will help you sort out your ideas, and it will be easier to read the next blog. Of course, I will try my best to write each article so that people who don’t understand the algorithm can read and understand it.
1. Introduction to dynamic rules
The idea of moving rules has five steps, and it is best to draw pictures to understand the details, don’t be afraid of trouble. When you start drawing pictures and read the questions carefully, you will experience the immersion in learning.
Status representation
state transition equation
initialization
Order of filling in the form
return value
Generally, dynamic rules will first create an array named dp. This array is also called dp table. Through some operations, the dp table is filled up, and one of the values is the answer. Each element of the dp array indicates a state. Our first step is to determine the state.
The status may be determined through the question requirements, the status may be determined through experience + question requirements, or the status may be determined by repeated sub-problems found during the analysis process. There are other ways to determine the status, but they are all similar. Once you understand the rules of movement, these ideas will also arise. The determination of the status is to determine what dp[i] is intended to represent. This is the most important step.
The state transition equation is what dp[i] is equal to, and what the state transition equation is. Like the Fibonacci sequence, dp[i] = dp[i – 1] + dp[i – 2]. This is the hardest step. At the beginning, the state representation may be incorrect, but it doesn’t matter. Make the state boldly. If the transfer equation cannot be derived and the result cannot be obtained, then the state representation is wrong. Therefore, state representation and state transition equations complement each other and can help you check your ideas.
Initialization means filling out the form to ensure that it does not cross the boundary. As mentioned in the first paragraph, the rule of thumb is to fill out a form. For example, in the Fibonacci sequence, if we want to fill in dp[1], then we may need dp[0] and dp[-1], which is out of bounds, so in order to prevent out of bounds, the first two values are fixed at the beginning. , then the third value is the sum of the first two values, and there will be no out-of-bounds.
The order of filling in the form. When filling in the current status, the required status should have been calculated. It is still the Fibonacci sequence. When filling in dp[4], dp[3] and dp[2] should have been calculated, then dp[4] will come out. The order at this time is from left to right. .
The return value depends on the question requirements.
2. The Nth Tabonacci sequence
1137. Nth Tabonacci number
The Tabonacci sequence starts from T0 instead of 1. This is also different from the Fibonacci sequence, but in essence the ideas are very similar. Next we need to use dynamic programming to solve the problem.
In this question, we let each element of the dp table store a Tabonacci sequence, with 0 subscript corresponding to T0 and 1 subscript corresponding to T1. Why is it determined to be in this state? The question requires getting the value of Tn, and there is also T0, which is consistent with the array subscript, so we’d better fill in all the numbers, and then use n as the subscript, and dp[n] can get the result at once.
According to the above analysis, we write like this
int tribonacci(int n) {<!-- -->
//1. State representation: dp[i] is the i-th Tabonacci number
//2. State transition equation: The question is given, Tn + 3 = Tn + Tn + 1 + Tn + 2
//Handle boundary cases. If n is less than 3, then it can only take 0, 1, 2. You can also go through the following loop, but it is better to return the corresponding value before creating the dp table to reduce space consumption.
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
vector<int> dp(n + 1);
dp[0] = 0, dp[1] = dp[2] = 1;//3. Initialization
for(int i = 3; i <= n; i + + )
{<!-- -->
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];//4. The order of filling in the table also reflects the state transition equation
}
return dp[n];//5. Return value
}
This question can also be optimized for space. To optimize space in dynamic rules, rolling arrays are usually used. When a state only needs several previous states to determine, a rolling array can be used. The space complexity of N^2 can be optimized to N. When dp[3] is determined, we set the first four values to abcd. Initially, a is dp[0], b is dp[1], c is dp[2], and d is dp[3]. To calculate dp [4], let abcd move back one place, that is, a is dp[1], d is dp[4], then d = a + b + c, find dp[4], calculate dp[ 5], still the same operation, let a come to the position of dp[2], and d is dp[5]. We can create a small array to store these variables, or we can create just four variables. When starting to scroll, we let a = b, b = c, c = d so that we can scroll, but we cannot assign values in reverse, that is, c = d, b = c, a = b because b wants to be before c The value of c has been assigned to d, so it doesn’t work. After using variables to evaluate, we no longer need the dp table and only use four variables to obtain the result.
int tribonacci(int n) {<!-- -->
//1. State representation: dp[i] is the i-th Tabonacci number
//2. State transition equation: The question is given, Tn + 3 = Tn + Tn + 1 + Tn + 2
//Handle boundary cases. If n is less than 3, then it can only take 0, 1, 2. You can also go through the following loop, but it is better to return the corresponding value before creating the dp table to reduce space consumption.
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int a = 0, b = 1, c = 1, d = 0;//3. Initialization
for(int i = 3; i <= n; i + + )
{<!-- -->
d = a + b + c;//4. Order
a = b; b = c; c = d;//After the loop ends, d is the final value
}
return d;//5. Return value
}
3. Three-step question
Interview questions 08.01. Three-step question
Can it be 1, 2, or 3? How should this state transition equation be calculated? Don’t rush yet, just look at the questions step by step. According to the title, we can know that when the state reaches position i, there are several ways in total, and dp[i] records the number of ways. The next step is to find the state transition equation. Although the question has three calculations, we might as well count a few values to see. When n = 1, 2, 3, and 4, they are 1, 2, 4, and 7 respectively. If we carefully add the number of methods for each n value , you will find that each n value is the sum of the previous three n values, such as 1 + 2 + 4 = 7, so this question is regular, then its state transition equation is dp[i] = dp[i – 1 ] + dp[i – 2] + dp[i – 3]. Starting from 1, dp[1], dp[2], and dp[3] are initialized to 1, 2, and 4 respectively. The order of filling in the form is from left to right. The return value is dp[n].
Since the number in this question will be too large, you need to take the modulo. If you add 3 numbers and then take the modulo, it will not pass. If you want to add 2 numbers, take the modulo, and then take the modulo as a whole.
int waysToStep(int n) {<!-- -->
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
const int MOD = 1e9 + 7;
vector<int> dp(n + 1);
dp[1] = 1, dp[2] = 2, dp[3] = 4;
for(int i = 4; i <= n; i + + )
{<!-- -->
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
}
return dp[n];
}
Of course, this question can also be space optimized, just like the previous question.
int waysToStep(int n) {<!-- -->
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
const int MOD = 1e9 + 7;
int a = 1, b = 2, c = 4, d = 0;
for(int i = 4; i <= n; i + + )
{<!-- -->
d = ((a + b) % MOD + c) % MOD;
a = b; b = c; c = d;
}
return d;
}
4. Climb the stairs with minimum cost
746. Climb the stairs with minimum cost
10, 15, 20. When you are at position 10, you will spend 10 yuan to go back once or twice. When you are at position 15, you will spend 15 yuan to go back once or twice. But the rightmost element in the given array is not the roof. All elements are stairs. The roof is at the next position of the last element. For example, in example 1, at position 15, it costs 15 yuan to span 2 stairs at one time. , arrived at the top of the building.
What is the status representation of this question? Like a one-dimensional dp array, according to the above two questions, the state is expressed at the end of the i position. The same is true for this question. Calculate the minimum amount of money required to reach the i position, so dp[1], dp[2 ] is the minimum cost to reach positions 1 and 2.
How to determine the state transition equation? Seeing now, we can summarize a rule and use the previous or subsequent state to deduce the value of dp[i]. For example, dp[i] is composed of dp[i – 1], dp[i – 2], etc. or dp[ i + 1], dp[i + 2] to determine. From this question, dp[i] either takes 1 step from i – 1 to reach i, or takes 2 steps from i – 2 to reach i. In both cases, the value of dp[i] can be obtained by comparing the size, and dp[ i – 1], dp[i – 2] are derived before. So dp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i – 2]).
When initializing, to avoid going out of bounds, the first two positions need to be initialized. According to the question, we can start from position 0 or position 1, then these two positions can be initialized to 0. The order of filling in the form is from left to right. The return value is dp[i].
Based on the above analysis, write the code
int minCostClimbingStairs(vector<int> & amp; cost) {<!-- -->
int n = cost.size();
vector<int> dp(n + 1);
for(int i = 2; i <= n; i + + )
{<!-- -->
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
This question can also be written using another state representation. The above is the yii position as the end, this time it is the i position as the starting point. At this time, dp[i] is the minimum cost to reach the top of the building from position i. This i starts from 0.
How to determine the state transition equation this time? Starting from position i, you can take one step or two steps, so it is also divided into two situations. Take one step, from position i + 1 to the end point; take two steps, from position i + 2 to the end point, and then calculate i + 1 or The minimum cost is calculated at i + 2. The first case is dp[i + 1] + cost[i], the second case is dp[i + 2] + cost[i], whichever is smaller.
How should this initialization be done? The last time we took dp[i – 1] and dp[i – 2], we initialized the two leftmost values. Now we take dp[i + 1] and dp[i + 2]. The easiest thing to determine is The two rightmost values, dp[n – 1] and dp[n – 2], are the money spent at the current position respectively. The order of filling out the form this time is from right to left. The return value is the minimum value of dp[0] and dp[1], and the top of the building is at position n.
The idea is actually similar, but in reverse. The array opened this time does not need n + 1. Before, we needed to calculate to dp[n], but now n – 1 is the starting point.
int minCostClimbingStairs(vector<int> & amp; cost) {<!-- -->
int n = cost.size();
/*vector<int> dp(n + 1);
for(int i = 2; i <= n; i + + )
{
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];*/
vector<int> dp(n);
dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
for(int i = n - 3; i >= 0; i--)
{<!-- -->
dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];//Because a cost[i] must be added, it is proposed
}
return min(dp[0], dp[1]);
}
5. Decoding method
91. Decoding method
The above analysis can still be used for this question. We first represent the state as ending with the i position. The string has i characters, and the number at position i should be the total number of characters that can be encoded from the first character to position i, so dp[i] is the total number of decoding methods when it ends at position i.
How to determine the state transition equation? Based on the analysis of the above questions, we know that we need to divide the problem according to the most recent step. The i position may be able to be encoded, and the i – 1 and i positions may also be able to be encoded. Since it ends with the i position, so i Regardless of i + 1, the i – 2 positions cannot be combined for encoding because the number represented by the letter is at most two digits, so this can help us determine the equation.
Now there are two situations, dp[i] is decoded alone, and dp[i- 1] and dp[i] are decoded in combination. Each situation has success or failure. If dp[i] can be decoded successfully, it means that all encoding schemes from 0 to i – 1 are followed by a character at position i, so at this time dp[i] The number of plans is the number of plans of dp[i – 1]. If dp[i] fails to encode alone, then all previous decodable solutions have failed, then it is 0.
dp[i – 1] and dp[i] decoding, there are also success and failure. If successful, then the number corresponding to the character at i – 1 multiplied by 10 + the number corresponding to the character at i should be >= 10 & & <= 26. Because the question says that 06 is impossible, so only Can be a normal two-digit number, 10 and above. Consider i - 1 and i as a whole. At this time, it is equivalent to adding two characters after all the plans of dp[i - 2], so it is the number of plans of dp[i - 2]. If it fails, the same is true. All the previous ones have failed and are 0.
According to the above analysis, dp[i] = dp[i – 1] + dp[i – 2], but these two do not necessarily add up, and may be 0.
How should initialization be done? There are two methods. Since dp[i] is determined by the first two positions, you must consider dp[0] and dp[1] during initialization. dp[0] is either 1 or 0. It has only one character, dp[ 1] represents two types of characters. It is one case that two characters can be decoded individually. It is another case that two characters can be decoded in combination. If one of them is satisfied, it is 1, if both are satisfied, it is 2, and if neither is satisfied, it is 0. So dp[1] has three cases: 0, 1, and 2.
The order of filling in the form is from left to right. As for the return value, we need to decode to the last position, so it should be dp[n – 1].
int numDecodings(string s) {<!-- -->
int n = s.size();
vector<int> dp(n);
dp[0] = s[0] != '0' ? 1 : 0;//Determine whether dp[0] can be decoded independently
if(n == 1) return dp[0];//Handle edge cases
if(s[0] != '0' & amp; & amp; s[1] != '0') dp[1] + = 1;//Determine whether dp[0]dp[1] can be alone decoding
int t = (s[0] - '0') * 10 + s[1] - '0';
if(t >= 10 & amp; & amp; t <= 26) dp[1] + = 1;//Determine whether the dp[0]dp[1] combination can be decoded
for(int i = 2; i < n; i + + )
{<!-- -->
if(s[i] != '0') dp[i] + = dp[i - 1];//Judge whether it can be decoded individually
int t = (s[i - 1] - '0') * 10 + s[i] - '0'; // Determine whether combined decoding is possible
if(t >= 10 & amp; & amp; t <= 26) dp[i] + = dp[i - 2];
}
return dp[n - 1];
}
Now write another initialization method. As can be seen from the above code, some code sections are repeated.
if(s[0] != '0' & amp; & amp; s[1] != '0') dp[1] + = 1;//Determine whether dp[0]dp[1] can No, both are decoded separately
int t = (s[0] - '0') * 10 + s[1] - '0';
if(t >= 10 & amp; & amp; t <= 26) dp[1] + = 1;//Determine whether the dp[0]dp[1] combination can be decoded
if(s[i] != '0') dp[i] + = dp[i - 1];//Judge whether it can be decoded individually
int t = (s[i - 1] - '0') * 10 + s[i] - '0'; // Determine whether combined decoding is possible
if(t >= 10 & amp; & amp; t <= 26) dp[i] + = dp[i - 2];
The previous dp represented [0, n – 1]. Now we extend it by an element and become [0, n]. Then the previous dp[1] is equivalent to the dp[2] of the new table. The previous dp [0] is the current dp[1], the previous dp[n – 1] is the new dp[n], and the dp[0] of the new table is a virtual node for more convenient initialization, as you can see below Where it works. There are some caveats to this method. One is to ensure that the character at position 1 in the string can correspond to dp[2], that is, to ensure the mapping relationship; the other is dp[0] in the new table, how to initialize it to ensure that the result is correct.
We want the loop to start from i = 2, using the same judgment method, dp[1] is not a problem, and dp[0], for dp[2], is dp[i – 2], then if the original string If the characters at positions 0 and 1 in the new table, that is, characters at positions 1 and 2 of the new table, can be combined and encoded, then it should be + dp[i – 2], which is + 1, so dp[0] should be initialized to 1.
The string starts from position 0, and the character at position 0 is judged, which corresponds to position 1 of the new table. i is moved in the new table, that is, i = 1 at this time, then the position of s[1 – 1] should be judged. , that is, the position of s[i – 1], the mapping relationship can be guaranteed.
int numDecodings(string s) {<!-- -->
int n = s.size();
//optimization
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = s[1 - 1] != '0' ? 1 : 0;//s[0]
for(int i = 2; i <= n; i + + )
{<!-- -->
if(s[i - 1] != '0') dp[i] + = dp[i - 1];//Judge whether it can be decoded individually
int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0'; // Determine whether combined decoding is possible
if(t >= 10 & amp; & amp; t <= 26) dp[i] + = dp[i - 2];
}
return dp[n];
}
6. Summary of dynamic rule analysis
The representation of status usually ends or starts from a certain position.
The determination of the state transition equation requires analysis of the most recent step
The second method of initialization is to set up a virtual node. The important thing to note is how to initialize the value of the virtual node to ensure that the results of filling in the table are correct, and to maintain the mapping relationship between the new table and the old table.
The order of filling out the forms depends on the analysis.
Finish.