C language daily practice - day 22: Zero foundation learning dynamic planning

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\le n\le 30)$, Find the number of Fibonacci series $n$ term .

2） Algorithm analysis

     Fibonacci sequence is a sequence from $0$ and $1$ Start , Each subsequent term is equal to the sum of the first two terms , Just like this. ：
$$\begin{gathered} F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2),Itsinn>1 \end{gathered}$$

     Get the title , Let's first look at the scope of the topic ,$n$ Not more than 30, That's because the Fibonacci number is growing very fast , It's exponential . So if $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)$ First define a loop variable ;
• $(2)$ Then define an array to record the... Of Fibonacci sequence $n$ term , And initialize the second $0$ term and The first $1$ term .
• $(3)$ Then one for loop , From 2 A start ;
• $(4)$ Use the recurrence formula to calculate the value of each item step by step ;
• $(5)$ Finally, return to No $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\le n\le 45)$ There are a total of $n$ Staircase , At first, on the $0$ rank , Every time I can climb $1$ perhaps $2$ A stair , Ask how many different ways you can climb to the roof .

2） Algorithm analysis

     We define an array $f[46]$, among $f[i]$ Says from the first $0$ Step up to step $i$ Number of schemes of order .

     Because you can climb every time $1$ perhaps $2$ A stair , So for the $i$ Take the stairs , So either from the first $i-1$ Climbing up the steps , Either from $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]$$
     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]$ 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]$ From the first $0$ Step to $0$ Number of schemes of order , Of course it is $1$ La ,$f[1]$ From the first $0$ Step to $1$ Number of schemes of order , Because I can only walk $1$ rank , So the number of schemes is also $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)$ First define a loop variable ;
• $(2)$ Define another array $f[i]$ From the first $0$ Step up to step $i$ Number of schemes of order ;
• $(3)$ Then one for loop , From 2 A start ;
• $(4)$ Use the recurrence formula to calculate the value of each item step by step ;
• $(5)$ Finally, return to No $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)$ perhaps $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\le 1000)$, Give me another one $n$ Array of integers $cost$, among $cost[i]$ It's from the stairs $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$ Or subscript $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]$ It means to climb to the first $i$ The minimum cost of layers .

Because you can only climb $1$ A or $2$ A stair , therefore $f[i]$ This state can only start from $f[i-1]$ perhaps $f[i-2]$ Turn around ：
    1） If from $i-1$ Climb up , The cost is $f[i-1]+cost[i-1]$;
    2） If from $i-2$ Climb up , The cost is $f[i-2]+cost[i-2]$;
     Nothing else , And we're going to The minimum cost is required , therefore $f[i]$ It should be the smaller of the two , The state transfer equation is obtained ：
$$f[i]=min(f[i-1]+cost[i-1],f[i-2]+cost[i-2])$$
     Then consider the initial situation $f[0]$ and $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)$ For the convenience of finding the minimum value , We implement a function with a minimum value $min$, Direct use of C Language Of Conditional operator That's all right. ;
• $(2)$ Then start the solution of dynamic programming , First define a loop variable ;
• $(3)$ Define another array $f[i]$ From the first $0$ Step up to step $i$ Minimum cost of order , And initialize the second $0$ term and The first $1$ term ;
• $(4)$ Then one for loop , From $2$ A start , The value of each term can be calculated by directly applying the state transition equation ;
• $(5)$ Finally, return to No $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\le n\le 100)$, Give me another one $n$ Array of integers $nums$, Each integer can be taken or not taken , If the first $i$ Take an integer , that The first $i-1$ perhaps $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$ In terms of integers , Each integer can be taken or not taken , So there are $2^n$ Secondary seed extraction . But the adjacent numbers can't all take , So the number of schemes is less than $2^n$ 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 $dp[i]$, Before presentation $i$ The maximum value of an integer that can be obtained by some selection scheme .
    1） If the first $i$ An integer is not taken , So the first $i-1$ There are two cases of taking and not taking , So it turns into $dp[i-1]$ The sub problem of ;

    2） If the first $i$ Take an integer , So the first $i-1$ One must not be taken , however The first $i-2$ There are two cases of taking and not taking an integer , So it turns into $dp[i-2]$ The sub problem of .

     So the state transfer equation is as follows ：
$$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$$
     Then let's look at the initial state , It's Yidi $0$ Maximum value at the end of elements . Of course, that's it ：
$$dp[0]=nums[0]$$
     Of course, in order to prevent the array subscript from crossing the bounds , By the end of $1$ The maximum value at the end of an element also needs to be found ：
$$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)$ The first requirement is the maximum , So we use conditional operators to simply implement a function for finding the maximum value ;
• $(2)$ Then start the solution of dynamic programming , First define a loop variable ;
• $(3)$ Define an array of States $dp[i]$, The initial state $dp[0]$ by $nums[0]$;
• $(4)$ Then a layer loop performs state transition ;
• $(5)$ To prevent calling $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)$ When i > 1 Just apply the state transition equation just studied ;
• $(7)$ Finally back to $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)$, So what is $O(1)$ Well ？ It is simply understood that the time of state transition is related to $n$ irrelevant , No matter $n$ How big? ,$i$ The state of must be from $i-1$ perhaps $i-2$ Transferred , So each state transition can be calculated twice at most .$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\le n\le 10^5)$, Re given $n$ No more than one. $10^4$ An array of integers $nums$, Each integer can be taken or not taken . If $x$ take , Then you will get $x$ Points , All values must be deleted after fetching $x-1$ and $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$, 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)$ First define a loop variable ;
• $(2)$ Then define two auxiliary arrays $sum[i]$ and $val[i]$, I will explain their functions later .
• $(3)$ take $sum$ Array utilization $memset$ Zeroing ;
• $(4)$ A layer of loops maps all numbers to $sum$ Array ,$sum[i]$ The value of represents $i$ The number of in the array ;
• $(5)$ Then fill in $val[i]$,$val[i]$ The value of represents the selection $i$ The number of points you can get later , Of course, it is its own value multiplied by its number , namely $i\times sum[i]$;
• $(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 $10^6$, 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\le n\le 10^5)$, Give me another one $n$ Array of integers $nums$, Please find one with The continuous subarray of the largest sum , Return to its maximum and .

2） Algorithm analysis

     about $n$ It's an integer , How many subarrays are there in total ？ We can enumerate the starting points 、 Enumerate endpoints , All in all $n\ast (n+1)/2$ Subarray , If you enumerate all subarrays , And then sum and maximize all sub arrays , There are three in all $for$ loop , The time complexity is $O(n^3)$, about $10^5$ 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 $dp[i]$ Says to the first $i$ The maximum value in an integer terminated subarray , By the end of $i$ The subarray ending with an integer is divided into two cases ：
    1、 And the $i-1$ A sub array ending in an integer ;
    2、 And the $i-1$ Subarrays ending in integers are not connected （ That is, both the starting point and the ending point are the first $i$ An integer ）;
     The larger of these two cases is the solution we require , So we can get the state transition equation as follows
$$dp[i]=max(dp[i-1]+nums[i],nums[i])$$
     Then let's look at the initial state , It's Yidi $0$ Maximum value at the end of elements , Of course, that's it
$$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)$ Define a function to find the maximum ;
• $(2)$ Define a loop variable ;
• $(3)$ Define an array of States $dp[i]$ ;
• $(4)$ Define a maximum value we want to return , Initialize to the value of the first integer ;
• $(5)$ Calculate the initial state $dp[0]$;
• $(6)$ Use a layer of circulation , Perform state transition ;
• $(7)$ And then in all the first $i$ Take a maximum value from the sub array at the end of an integer ;
• $(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)$, The state transition time complexity of a single state is $O(b)$, Then the time complexity of the solution process of the whole dynamic programming is $O(ab)$.
     linear DP The number of States is $O(n)$, The time complexity of state transition is generally $O(1)$ perhaps $O(n)$, Also have $O(lo{g}_{2}n)$ 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 .