Tag dynamic programming - preliminary knowledge for question brushing -1 Dynamic programming five part problem solving method + lt.509 Fibonacci number / Sword finger offer 10 I + lt.70. Climbing stai

Initial understanding of dynamic programming

Dynamic programming : DP, If a problem has many overlapping subproblems , Using dynamic programming is the most effective , Therefore, every state in dynamic programming must be derived from the previous state , This is different from greed ,

• Greed has no state , But choose the best one directly from the local

As we all know The dynamic gauge is made of ** The previous state ** Derived from , Greed is the local direct selection of the optimal , It is enough to brush the questions .

Problem solving steps of dynamic programming

• State transition formula ( The recursive formula ) Very important , But the dynamic gauge is not just a recursive formula !

Five steps of dynamic programming

1. determine dp Array (dp table) And subscripts The meaning of ;
2. determine The recursive formula
3. dp How to initialize an array
4. determine traversal order
5. Give an example to deduce dp Array

DP What's the problem Debug

How to calculate the time complexity of recursive algorithm ？ It is to multiply the number of subproblems by the time needed to solve a subproblem .

lt.509. Fibonacci number

Case study

Train of thought analysis 1 , Recurrence of violence

The state transition equation has been given , We can get the answer directly by recursion .

Train of thought analysis II , Remove double counting , Use an array to record the calculated value

from f(n) = f(n - 1) + f(n - 2); It can be seen that f(n) Only the first two values are required for each calculation , We record the first two values in an array ;

1. determine dp Meaning of array and subscript
2. Determine the recurrence formula
3. dp Initialization of an array
4. Determine the traversal order , Sequential traversal
5. Give an example to deduce dp Array

class Solution {
    
    public int fib(int n) {
    
        // Two ,  Use an array to record each f(n - 1) and f(n - 2);
        //1.  determine dp Meaning of array and subscript ,  requirement f(n),  There has to be dp(n),  So the array length is n+1;
        int[] dp = new int[n + 1];
        //2.  Determine the recurrence formula ,  Has been given ; f(n) = f(n - 1) + f(n - 2);
        //3. dp Initialization of an array ,  Has been given 
        if(n == 0 || n == 1)return n;
        dp[0] = 0;
        dp[1] = 1;

        //4.  Determine the traversal order ,  Sequential traversal , 
        for(int i = 2; i <= n; i++){
    
            dp[i] = dp[i- 1] + dp[i- 2];
        }

        return dp[n];
    }
}

Train of thought Analysis III , Optimize the space complexity

from f(n) = f(n - 1) + f(n - 2); It can be seen that f(n) Only the first two values are required for each calculation , We maintain two variables directly , Keep updating ;

class Solution {
    
    public int fib(int n) {
    
        // 3、 ... and , 
        if(n == 0 || n == 1)return n;
        int dp2 = 0;
        int dp1 = 1;

        int dp = 0;
        for(int i = 2; i <= n; i++){
    
            dp = dp1 + dp2;
            dp2 = dp1; // Note that there ,  The order must not be disordered !  The first dp[n-1] The value is assigned to dp[n-2];
            dp1 = dp;//  And then dp[n] The value is assigned to dp[n - 1];
        }
        return dp;
    }
}

The finger of the sword Offer 10- I. Fibonacci sequence

Case study

Thought analysis : Strike while the iron is hot , Use the third method above directly

This question is based on the above one , It is required to take the mold during the calculation

class Solution {
    
    public int fib(int n) {
    
        if(n == 0 || n == 1)return n;

        int dp2 = 0;
        int dp1 = 1;

        int dp = 0;

        for(int i = 2; i <= n; i++){
    
            dp = (dp1 + dp2) % 1000000007;
            dp2 = dp1;
            dp1 = dp;
        }

        return dp;
    }
}

lt.70. climb stairs

Case study

Train of thought analysis 1 , DP Five steps

1. determine DP Array and subscript meaning

2. 1. dp[n] = x, n It means how many steps there are in the stairs , x It's on the stairs n The existing method of climbing stairs

3. Determine the recurrence formula ( State transition formula )

4. 1. The title gives , Can only climb at a time 1 Or climb 2 A stair , So we are climbing n A step , Only by 1 A step or 2 From the state transition of three steps .
   2. So the state transition formula is : dp[n] = dp[n - 1] + dp[n-2]; in other words , n-1 Possible ways to climb stairs ( There's still 1 A stair ) + n-2 Possible ways to climb stairs ( There's still 2 A stair )

5. dp How to initialize an array

6. 1. Can only climb at a time 1 A or 2 A stair , therefore dp[1] = 1, dp[2] = 2;

7. Determine the traversal order , From the perspective of recurrence formula , Sequential traversal .

8. (debug) Give an example to deduce dp Array .

class Solution {
    
    public int climbStairs(int n) {
    
        //1.  determine dp Array ,  He climbed i(n) A stair ,  Yes dp[i] Medium method 
        int[] dp = new int[n + 1];

        //2.  Determine the recurrence formula 
        //dp[i] = dp[i - 1] + dp[i - 2];
        //3. dp How to initialize an array 
        dp[1] = 1;
        dp[2] = 2;

        //4.  traversal order 
        // Reverse traversal ,  know n-1, n-2 A step method ,  Introduction n A step jump 
        int sum = 0;
        for(int i = 2; i <= n; i++){
    
            dp[i] = dp[i - 1] + dp[i - 2];
            sum += dp[i];
        }

        return sum;
    }
}

The two most common questions about climbing stairs

1. Why? f(n) = f(n - 1) + f(n - 2) ? How to think of ?

1. First , The title gives , Can only climb at a time 1 A stair , perhaps 2 A stair , Before we climb n A step , Only by climbing up n-1 Behind the steps , Climb again 1 A stair , Or climb n-2 Behind the steps , Climb again 2 A stair

2. Some people may have such doubts , Why? (n-1) The climbing method of steps and (n-2) The climbing method of steps , No repetition ?

3. 1. First climb n-1 And climb n-2 The number of steps is different , How can I repeat ? These are two complete cases ! We climb n-1 Climb the stairs 1 Steps have arrived n steps , We climb n In the case of steps , Climb again 2 A step has been reached n steps .

4. Then some people may have the following questions , Why can't we finish climbing n-2 After mediation , Climb again 1 Steps and 1 A stair , Or climb again 2 Two steps ?

5. 1. –> You are climbing n-2 Behind the steps , One more step , It doesn't mean you've climbed ahead n-1 There are various ways to climb the steps .

2. Why climb n-1 In the case of step , There is still one order left , Or climb n-2 There are two steps left , Why not add 1 or 2 Well ?

Actually, I am climbing n-1 In this case , We have various combinations of climbing methods , But the distance climbs n rank , We can only climb again 1 A stair , This 1 Namely n-1 After a step climb , Climb again n The only case of a step ;

Empathy , We are finishing the climb n-2 steps , Got it n-2 After all kinds of climbing methods of steps , I can only climb again 2 Steps to get n A stair .

Just to give you an example ,

The interview questions about climbing stairs (dbc)

1. Expand 1

2. Expand 2

3. Expand 3

4. Expand 4

5. Expand 5