当前位置:网站首页>C language daily practice - day 22: Zero foundation learning dynamic planning
C language daily practice - day 22: Zero foundation learning dynamic planning
2022-07-06 19:08:00 【Where do heroes come from】
List of articles
One 、 Preface
In the previous article , I have talked about some classic dynamic programming , for example : The longest single tone subsequence 、 Longest common subsequence 、 Minimum edit distance 、 knapsack problem 、 Memory search 、 Section DP、 digit DP, There are some difficult contents , It's not easy to understand , So this article , I will sort out the basic dynamic planning , From the simplest linear DP Start talking about , Let's talk about how to figure out the dynamic planning step by step .
Click the end of the article 【 Read the original 】 You can jump to the video explanation .
Two 、 Recurrence
First let's take a look at , A problem that must be seen before zero foundation learning dynamic planning .
1、 Fibonacci sequence
1) Title Description
Given a n ( 0 ≤ n ≤ 30 ) n (0 \le n \le 30) n(0≤n≤30), Find the number of Fibonacci series n n n term .
2) Algorithm analysis
Fibonacci sequence is a sequence from 0 0 0 and 1 1 1 Start , Each subsequent term is equal to the sum of the first two terms , Just like this. :
F ( 0 ) = 0 F ( 1 ) = 1 F ( n ) = F ( n − 1 ) + F ( n − 2 ) , Its in n > 1 F(0) = 0 \\ F(1) = 1 \\ F(n) = F(n - 1) + F(n - 2), among n > 1 F(0)=0F(1)=1F(n)=F(n−1)+F(n−2), Its in n>1
Get the title , Let's first look at the scope of the topic , n n n Not more than 30, That's because the Fibonacci number is growing very fast , It's exponential . So if n n n It's big , It will surpass c Language in 32 The range of bit integers . This is the most basic recursive problem , The recurrence formula has told you , All we have to do is use a loop to achieve this recursion .
3) Source details
int fib(int n) {
int i; // (1)
int f[31] = {
0, 1}; // (2)
for(i = 2; i <= n; ++i) {
// (3)
f[i] = f[i-1] + f[i-2]; // (4)
}
return f[n]; // (5)
}
- ( 1 ) (1) (1) First define a loop variable ;
- ( 2 ) (2) (2) Then define an array to record the... Of Fibonacci sequence n n n term , And initialize the second 0 0 0 term and The first 1 1 1 term .
- ( 3 ) (3) (3) Then one for loop , From 2 A start ;
- ( 4 ) (4) (4) Use the recurrence formula to calculate the value of each item step by step ;
- ( 5 ) (5) (5) Finally, return to No n n n Item can .
4) Simple reply
Recursion is actually one of the simplest state transitions , If the concept of state is still vague , It doesn't matter. . What's next , I will constantly instill the concept of state into you , Next, let's look at another problem , It is a simple application of Fibonacci sequence .
2、 climb stairs
1) Title Description
Given a n ( 1 ≤ n ≤ 45 ) n (1 \le n \le 45) n(1≤n≤45) There are a total of n n n Staircase , At first, on the 0 0 0 rank , Every time I can climb 1 1 1 perhaps 2 2 2 A stair , Ask how many different ways you can climb to the roof .
2) Algorithm analysis
We define an array f [ 46 ] f[46] f[46], among f [ i ] f[i] f[i] Says from the first 0 0 0 Step up to step i i i Number of schemes of order .
Because you can climb every time 1 1 1 perhaps 2 2 2 A stair , So for the i i i Take the stairs , So either from the first i − 1 i-1 i−1 Climbing up the steps , Either from i − 2 i-2 i−2 Climbing up the steps , As shown in the figure :
So we get a recursive formula
f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i] = f[i-1] + f[i-2] f[i]=f[i−1]+f[i−2]
We found that this is the Fibonacci sequence , You can call it a recursive formula , It can also be called the state transition equation . there f [ i ] f[i] f[i] Is the concept of state , From one state to another is called state transition .
Of course, we also need to consider the initial state , f [ 0 ] f[0] f[0] From the first 0 0 0 Step to 0 0 0 Number of schemes of order , Of course it is 1 1 1 La , f [ 1 ] f[1] f[1] From the first 0 0 0 Step to 1 1 1 Number of schemes of order , Because I can only walk 1 1 1 rank , So the number of schemes is also 1 1 1.
3) Source details
int climbStairs(int n){
int i; // (1)
int f[46] = {
1, 1}; // (2)
for(i = 2; i <= n; ++i) {
// (3)
f[i] = f[i-1] + f[i-2]; // (4)
}
return f[n]; // (5)
}
- ( 1 ) (1) (1) First define a loop variable ;
- ( 2 ) (2) (2) Define another array f [ i ] f[i] f[i] From the first 0 0 0 Step up to step i i i Number of schemes of order ;
- ( 3 ) (3) (3) Then one for loop , From 2 A start ;
- ( 4 ) (4) (4) Use the recurrence formula to calculate the value of each item step by step ;
- ( 5 ) (5) (5) Finally, return to No n n n Item can .
4) Simple reply
Through this question, we find , A question can be asked in different ways , But the final solution is the same . How to transform complex problems into what we have learned is the ability to abstract problems , The word abstract is very abstract , It takes constant practice to understand the essence .
3、 ... and 、 linear DP
Recursion is also linear in a sense DP, linear DP The biggest feature of is that the state is represented by a one-dimensional array , The time complexity of general state transition is O ( 1 ) O(1) O(1) perhaps O ( n ) O(n) O(n).
Let's look at a linear DP To deepen our understanding .
1、 Use the minimum cost to climb the stairs
1) Title Description
Given a n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000), Give me another one n n n Array of integers c o s t cost cost, among c o s t [ i ] cost[i] cost[i] It's from the stairs i i i The cost of climbing a step up . Once this fee is paid , You can choose to climb up one or two steps .
You can choose to subscript 0 0 0 Or subscript 1 1 1 The steps began to climb the stairs , Please calculate and return the minimum cost to reach the top of the stairs .
2) Algorithm analysis
We found that this question is very similar to the previous question of climbing stairs , Only from the original number of calculation schemes to the minimum cost of calculation .
We try to use an array to represent the state : f [ i ] f[i] f[i] It means to climb to the first i i i The minimum cost of layers .
Because you can only climb 1 1 1 A or 2 2 2 A stair , therefore f [ i ] f[i] f[i] This state can only start from f [ i − 1 ] f[i-1] f[i−1] perhaps f [ i − 2 ] f[i-2] f[i−2] Turn around :
1) If from i − 1 i-1 i−1 Climb up , The cost is f [ i − 1 ] + c o s t [ i − 1 ] f[i-1] + cost[i-1] f[i−1]+cost[i−1];
2) If from i − 2 i-2 i−2 Climb up , The cost is f [ i − 2 ] + c o s t [ i − 2 ] f[i-2] + cost[i-2] f[i−2]+cost[i−2];
Nothing else , And we're going to The minimum cost is required , therefore f [ i ] f[i] f[i] It should be the smaller of the two , The state transfer equation is obtained :
f [ i ] = m i n ( f [ i − 1 ] + c o s t [ i − 1 ] , f [ i − 2 ] + c o s t [ i − 2 ] ) f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]) f[i]=min(f[i−1]+cost[i−1],f[i−2]+cost[i−2])
Then consider the initial situation f [ 0 ] f[0] f[0] and f [ 1 ] f[1] f[1], According to the title requirements, they should all be 0.
3) Source details
int min(int a, int b) {
return a < b ? a : b; // (1)
}
int minCostClimbingStairs(int* cost, int n){
int i; // (2)
int f[1001] = {
0, 0}; // (3)
for(i = 2; i <= n; ++i) {
// (4)
f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);
}
return f[n]; // (5)
}
- ( 1 ) (1) (1) For the convenience of finding the minimum value , We implement a function with a minimum value m i n min min, Direct use of C Language Of Conditional operator That's all right. ;
- ( 2 ) (2) (2) Then start the solution of dynamic programming , First define a loop variable ;
- ( 3 ) (3) (3) Define another array f [ i ] f[i] f[i] From the first 0 0 0 Step up to step i i i Minimum cost of order , And initialize the second 0 0 0 term and The first 1 1 1 term ;
- ( 4 ) (4) (4) Then one
for
loop , From 2 2 2 A start , The value of each term can be calculated by directly applying the state transition equation ; - ( 5 ) (5) (5) Finally, return to No n n n Item can ;
4) Simple reply
This is just the simplest introduction to dynamic planning , Relatively simple , The simpler it is, the more we can sum up the rules . By doing these three questions , We can summarize the general process of brushing dynamic programming questions :
1、 Design status
2、 Write the equation of state transition
3、 Set the initial state
4、 Perform state transition
5、 Return to the final solution
Let's try to do an advanced problem to find our feelings .
2、 raid homes and plunder houses
1) Title Description
Given an integer n ( 1 ≤ n ≤ 100 ) n (1 \le n \le 100) n(1≤n≤100), Give me another one n n n Array of integers n u m s nums nums, Each integer can be taken or not taken , If the first i i i Take an integer , that The first i − 1 i-1 i−1 perhaps i + 1 i+1 i+1 An integer cannot be taken .
It is required to select some integers according to the above rules , Make the sum of the selected integers maximum , Return this maximum .
2) Algorithm analysis
about n n n In terms of integers , Each integer can be taken or not taken , So there are 2 n 2^n 2n Secondary seed extraction . But the adjacent numbers can't all take , So the number of schemes is less than 2 n 2^n 2n Time of . However, it can be predicted that it is still exponential , So violent enumeration will definitely timeout .
So we define an array of States d p [ i ] dp[i] dp[i], Before presentation i i i The maximum value of an integer that can be obtained by some selection scheme .
1) If the first i i i An integer is not taken , So the first i − 1 i-1 i−1 There are two cases of taking and not taking , So it turns into d p [ i − 1 ] dp[i-1] dp[i−1] The sub problem of ;
2) If the first i i i Take an integer , So the first i − 1 i-1 i−1 One must not be taken , however The first i − 2 i-2 i−2 There are two cases of taking and not taking an integer , So it turns into d p [ i − 2 ] dp[i-2] dp[i−2] The sub problem of .
So the state transfer equation is as follows :
d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] ) dp[i] = max(dp[i-1], dp[i-2] + nums[i]) dp[i]=max(dp[i−1],dp[i−2]+nums[i])
Then let's look at the initial state , It's Yidi 0 0 0 Maximum value at the end of elements . Of course, that's it :
d p [ 0 ] = n u m s [ 0 ] dp[0] = nums[0] dp[0]=nums[0]
Of course, in order to prevent the array subscript from crossing the bounds , By the end of 1 1 1 The maximum value at the end of an element also needs to be found :
d p [ 1 ] = m a x ( n u m s [ 0 ] , n u m s [ 1 ] ) dp[1] = max(nums[0], nums[1]) dp[1]=max(nums[0],nums[1])
3) Source details
int max(int a, int b) {
return a > b ? a : b; // (1)
}
int rob(int* nums, int n){
int i; // (2)
int dp[110];
dp[0] = nums[0]; // (3)
for(i = 1; i < n; ++i) {
// (4)
if(i == 1) {
// (5)
dp[1] = max(nums[0], nums[1]);
}else {
// (6)
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
}
return dp[n-1]; // (7)
}
- ( 1 ) (1) (1) The first requirement is the maximum , So we use conditional operators to simply implement a function for finding the maximum value ;
- ( 2 ) (2) (2) Then start the solution of dynamic programming , First define a loop variable ;
- ( 3 ) (3) (3) Define an array of States d p [ i ] dp[i] dp[i], The initial state d p [ 0 ] dp[0] dp[0] by n u m s [ 0 ] nums[0] nums[0];
- ( 4 ) (4) (4) Then a layer loop performs state transition ;
- ( 5 ) (5) (5) To prevent calling d p [ i − 2 ] dp[i-2] dp[i−2] The array subscript is out of bounds , When
i == 1
The situation requires special treatment , It's also relatively simple , Is either take the first 0 One or the second 1 individual ; - ( 6 ) (6) (6) When
i > 1
Just apply the state transition equation just studied ; - ( 7 ) (7) (7) Finally back to d p [ n − 1 ] dp[n-1] dp[n−1] That's the answer we asked for ;
4) Simple reply
This problem is a basic linear DP topic , It's basically the same as climbing stairs . It is called linear because there is a linear relationship between the number of States and the time complexity , yes O(n) Of .
The time complexity of state transition of each state is O ( 1 ) O(1) O(1), So what is O ( 1 ) O(1) O(1) Well ? It is simply understood that the time of state transition is related to n n n irrelevant , No matter n n n How big? , i i i The state of must be from i − 1 i-1 i−1 perhaps i − 2 i-2 i−2 Transferred , So each state transition can be calculated twice at most . O ( 1 ) O(1) O(1) The meaning of is more representative of constant time complexity .
3、 Delete and get points
1) Title Description
Given an integer n ( 1 ≤ n ≤ 1 0 5 ) n (1\le n \le 10^5) n(1≤n≤105), Re given n n n No more than one. 1 0 4 10^4 104 An array of integers n u m s nums nums, Each integer can be taken or not taken . If x x x take , Then you will get x x x Points , All values must be deleted after fetching x − 1 x-1 x−1 and x + 1 x+1 x+1 The integer of .
It is required to select some integers according to the above rules , Make the sum of the selected integers maximum , Return this maximum .
2) Algorithm analysis
For this question , We can find that the range of integers does not exceed 10000 10000 10000, Making good use of this condition is the key to successful problem solving . Because the number is not big , So we can map all the numbers into the array , Then, after a certain number is taken, the adjacent number cannot be taken , Why ??? This is the problem of robbing families .
3) Source details
int max(int a, int b) {
return a > b ? a : b;
}
int rob(int* nums, int n){
int i;
int dp[10010];
dp[0] = nums[0];
for(i = 1; i < n; ++i) {
if(i == 1) {
dp[1] = max(nums[0], nums[1]);
}else {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
}
return dp[n-1];
}
int deleteAndEarn(int* nums, int n){
int i; // (1)
int sum[10010], val[10010]; // (2)
memset(sum, 0, sizeof(sum)); // (3)
for(i = 0; i < n; ++i) {
++sum[ nums[i] ]; // (4)
}
for(i = 0; i <= 10000; ++i) {
val[i] = i * sum[i]; // (5)
}
return rob(val, 10001); // (6)
}
- ( 1 ) (1) (1) First define a loop variable ;
- ( 2 ) (2) (2) Then define two auxiliary arrays s u m [ i ] sum[i] sum[i] and v a l [ i ] val[i] val[i], I will explain their functions later .
- ( 3 ) (3) (3) take s u m sum sum Array utilization m e m s e t memset memset Zeroing ;
- ( 4 ) (4) (4) A layer of loops maps all numbers to s u m sum sum Array , s u m [ i ] sum[i] sum[i] The value of represents i i i The number of in the array ;
- ( 5 ) (5) (5) Then fill in v a l [ i ] val[i] val[i], v a l [ i ] val[i] val[i] The value of represents the selection i i i The number of points you can get later , Of course, it is its own value multiplied by its number , namely i × s u m [ i ] i \times sum[i] i×sum[i];
- ( 6 ) (6) (6) And then directly put Copy the code of home robbery , Modify the array range , Just call it directly ;
4) Simple reply
This problem , It needs a sharp turn , Of course, there is also an element of experience , See that the number range is less than 1 0 6 10^6 106, Basically, we need to think about whether we can map to array subscripts , So as to transform the problem into the problem we have learned .
4、 Maximum subarray and
1) Title Description
Given an integer n ( 1 ≤ n ≤ 1 0 5 ) n (1 \le n \le 10^5) n(1≤n≤105), Give me another one n n n Array of integers n u m s nums nums, Please find one with The continuous subarray of the largest sum , Return to its maximum and .
2) Algorithm analysis
about n n n It's an integer , How many subarrays are there in total ? We can enumerate the starting points 、 Enumerate endpoints , All in all n ∗ ( n + 1 ) / 2 n*(n+1)/2 n∗(n+1)/2 Subarray , If you enumerate all subarrays , And then sum and maximize all sub arrays , There are three in all f o r for for loop , The time complexity is O ( n 3 ) O(n^3) O(n3), about 1 0 5 10^5 105 The order of magnitude , This time complexity is obviously unacceptable . Let's use the routine of dynamic programming , Recall the question brushing process of dynamic programming :
1、 Design status
2、 Write the equation of state transition
3、 Set the initial state
4、 Perform state transition
5、 Return to the final solution
So we define an array of States d p [ i ] dp[i] dp[i] Says to the first i i i The maximum value in an integer terminated subarray , By the end of i i i The subarray ending with an integer is divided into two cases :
1、 And the i − 1 i-1 i−1 A sub array ending in an integer ;
2、 And the i − 1 i-1 i−1 Subarrays ending in integers are not connected ( That is, both the starting point and the ending point are the first i i i An integer );
The larger of these two cases is the solution we require , So we can get the state transition equation as follows
d p [ i ] = m a x ( d p [ i − 1 ] + n u m s [ i ] , n u m s [ i ] ) dp[i] = max(dp[i-1] + nums[i], nums[i]) dp[i]=max(dp[i−1]+nums[i],nums[i])
Then let's look at the initial state , It's Yidi 0 0 0 Maximum value at the end of elements , Of course, that's it
d p [ 0 ] = n u m s [ 0 ] dp[0] = nums[0] dp[0]=nums[0]
3) Source details
int max(int a, int b) {
return a > b ? a : b; // (1)
}
int maxSubArray(int* nums, int n){
int i; // (2)
int dp[100001]; // (3)
int maxValue = nums[0]; // (4)
dp[0] = nums[0]; // (5)
for(i = 1; i < n; ++i) {
// (6)
dp[i] = max(dp[i-1] + nums[i], nums[i]);
maxValue = max(maxValue, dp[i]);// (7)
}
return maxValue; // (8)
}
- ( 1 ) (1) (1) Define a function to find the maximum ;
- ( 2 ) (2) (2) Define a loop variable ;
- ( 3 ) (3) (3) Define an array of States d p [ i ] dp[i] dp[i] ;
- ( 4 ) (4) (4) Define a maximum value we want to return , Initialize to the value of the first integer ;
- ( 5 ) (5) (5) Calculate the initial state d p [ 0 ] dp[0] dp[0];
- ( 6 ) (6) (6) Use a layer of circulation , Perform state transition ;
- ( 7 ) (7) (7) And then in all the first i i i Take a maximum value from the sub array at the end of an integer ;
- ( 8 ) (8) (8) Finally, returning the maximum value is the answer we require ;
4) Simple reply
This problem is obviously more difficult than the previous one , You can watch it a few more times , Think about it , Use all the fragmented time to learn , It will come out sooner or later , Then think about it , Good luck !
Four 、 Summary and resumption
1、 state
If you have learned the principle of compilation , Then you should know DFA ( Finite state automata ), you 're right , The state here can be understood as the state in the state machine , namely DFA A node on .
2、 State shift
State transition corresponds to DFA On the edge of , That is, from one state to another , There may also be conditions on the side , It corresponds to the condition of state transition .
3、 Time complexity
The time complexity of dynamic programming is divided into two parts : Time complexity of state calculation , State transition time complexity of each state .
The time complexity of all state calculations is O ( a ) O(a) O(a), The state transition time complexity of a single state is O ( b ) O(b) O(b), Then the time complexity of the solution process of the whole dynamic programming is O ( a b ) O(ab) O(ab).
linear DP The number of States is O ( n ) O(n) O(n), The time complexity of state transition is generally O ( 1 ) O(1) O(1) perhaps O ( n ) O(n) O(n), Also have O ( l o g 2 n ) O(log_2n) O(log2n) Of , It is possible to use binary enumeration for state transition , For example, the longest adjustment list .
4、 linear DP expand
Common linear DP There is the longest single tone subsequence 、 Prefix maximum 、 The prefix and 、 Backpacking problems and so on .
5、 Brush topic line
It can be passed through the official account 「 In the dead of night 」 reply 「 Problem set 」 obtain .
边栏推荐
- ROS custom message publishing subscription example
- 上海部分招工市场对新冠阳性康复者拒绝招录
- English topic assignment (25)
- Multithreading Basics: basic concepts of threads and creation of threads
- First day of rhcsa study
- Camel case with Hungarian notation
- Online notes
- Digital "new" operation and maintenance of energy industry
- Pychrm Community Edition calls matplotlib pyplot. Solution of imshow() function image not popping up
- R language ggplot2 visualization: use ggviolin function of ggpubr package to visualize violin diagram
猜你喜欢
Wx applet learning notes day01
ORACLE进阶(四)表连接讲解
MRO industrial products enterprise procurement system: how to refine procurement collaborative management? Industrial products enterprises that want to upgrade must see!
朗坤智慧冲刺科创板:年营收4亿 拟募资7亿
Xingnuochi technology's IPO was terminated: it was planned to raise 350million yuan, with an annual revenue of 367million yuan
LeetCode-1279. 红绿灯路口
ACTF 2022圆满落幕,0ops战队二连冠!!
深度循环网络长期血压预测【翻译】
Describe the process of key exchange
Helm deploy etcd cluster
随机推荐
LeetCode-1279. 红绿灯路口
中缀表达式转后缀表达式详细思路及代码实现
Collection of penetration test information -- use with nmap and other tools
R language uses DT function to generate t-distribution density function data and plot function to visualize t-distribution density function data
Graffiti intelligence is listed on the dual main board in Hong Kong: market value of 11.2 billion Hong Kong, with an annual revenue of 300 million US dollars
被疫情占据的上半年,你还好么?| 2022年中总结
test about BinaryTree
QPushButton绑定快捷键的注意事项
Leetcode topic [array] - 119 Yang Hui triangle II
wx小程序学习笔记day01
Synchronous development of business and application: strategic suggestions for application modernization
ACTF 2022圆满落幕,0ops战队二连冠!!
AutoCAD - what is the default lineweight for centerline drawing and CAD? Can I modify it?
Visual Studio Code启动时提示“Code安装似乎损坏。请重新安装。”、标题栏显示“不受支持”信息的解决办法
五金机电行业供应商智慧管理平台解决方案:优化供应链管理,带动企业业绩增长
The list of people who passed the fifth phase of personal ability certification assessment was published
Php+redis realizes the function of canceling orders over time
涂鸦智能在香港双重主板上市:市值112亿港元 年营收3亿美元
How to improve website weight
Word如何显示修改痕迹