Dynamic programming problem (1)

One 、 Fibonacci sequence

Solution 1 : recursive

class Solution {
    
public:
    int Fibonacci(int n) {
    
        if(n==1||n==2)
            return 1;
        else
            return Fibonacci(n-1)+Fibonacci(n-2);
    }
};

Time complexity ：O(2^n) Each recursion calls two recursions , So present 2 The exponential growth of
Spatial complexity ：O(n), The maximum depth of the recursive stack

Solution 2 : iteration ( recommend )

class Solution {
    
public:
    int Fibonacci(int n) {
    
        // from 0 Start , The first 0 Item is 0, The first is 1
        if(n <= 1)    
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         // because n=2 Shi yewei 1, When initializing a=0,b=1
         for (int i = 2; i <= n; i++){
    
         // The third item starts with the sum of the first two items , Then keep the latest two , Update data addition 
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
};

Time complexity ：O(n), among n Number entered for ,n Sub iteration
Spatial complexity ：O(1), Constant level variable , There is no additional auxiliary space

Solution 3 : Dynamic programming

• Create a length of n+1 Array of , Because only n+1n Can have subscript n term , Before we use it to record n Term Fibonacci sequence .
• According to the formula , Initializing page 0 Xiang and di 1 term （ In the title is 1 Xiang and di 2 term , It's essentially the same ）.
• Traversal array , According to the formula, a certain term is equal to the sum of the first two terms , Fill up the subsequent elements of the array , You can get fib[n]

class Solution {
    
public:
    int Fibonacci(int n) {
    
        if(n<=1)
            return n;
        int*fib=new int[n+1];
        fib[0]=0,fib[1]=1;
        for(int i=2;i<=n;i++)
            fib[i]=fib[i-1]+fib[i-2];
        return fib[n];
    }
};

Time complexity ：O(n), One for Loop traversal
Spatial complexity ：O(n), Created a size of n+1 Dynamic array of

Two 、 Skip step

Solution 1 : recursive

class Solution {
    
public:
    int jumpFloor(int number) {
    
        // Here I 0 Items for 1, The first 1 Items for 1
        if(number <= 1)
            return 1;
        else
            // Recursive subproblem addition 
            return jumpFloor(number - 1) + jumpFloor(number - 2);  
    }
};

Time complexity ：O(2^n), Each recursion calls two recursions , So present 2 The exponential growth of
Spatial complexity ：O(n), The maximum depth of stack space is n

Solution 2 : Recursive optimization

• Use dp Array records the value of the previous sequence .
• Function below 2 Sequence of terms , Go straight back to 1.
• For the present n, If dp If it exists in the array, it can be used directly , Otherwise, recursively call the function to calculate the sum of the two sub problems .

class Solution {
    
public:
    // Set global variables , Because there is no 0, Available 0 Make the initial identification value 
    int dp[50] = {
    0};
    int F(int n){
    
        if(n <= 1)
            return 1;
        // if dp If there is a value in, you don't need to recursively add it again 
        if(dp[n] != 0)   
            return dp[n];
        // if dp If there is no value in, you need to recursively add it again 
        return dp[n] = F(n - 1) + F(n - 2);
    }
    int jumpFloor(int number) {
    
        return F(number);
    }
};

Time complexity ： Each number is calculated only once , So it's O(n)
Spatial complexity ：O(n), Maximum depth of stack space

Solution 3 : Iterative addition ( recommend )

• lower than 2 Sequence of terms , Go straight back to n.
• Initializing page 0 term , With the first 1 Items are 0,1.
• From 2 A start , Gradually accumulate according to the formula , And update the addition number to always be the first two items of the next item .

class Solution {
    
public:
    int jumpFloor(int number) {
    
        // from 0 Start , The first 0 Item is 0, The first is 1
        if(number <= 1)    
            return 1;
        int res = 0;
        int a =1;
        int b = 1;
        // because n=2 Shi yewei 1, When initializing a=0,b=1
        for(int i = 2; i <= number; i++){
    
        // The third item starts with the sum of the first two items , Then keep the latest two , Update data addition 
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }
};

Time complexity ：O(n), among nnn Number entered for
Spatial complexity ：O(1), Constant level variable , There is no additional auxiliary space

Method four : Dynamic programming

class Solution {
    
public:
    int jumpFloor(int number) {
    
        if(number<=1)
            return 1;
        int*res=new int[number+1];
        res[0]=1,res[1]=1;
        for(int i=2;i<=number;i++)
            res[i]=res[i-1]+res[i-2];
        return res[number];
    }
};

Time complexity ：O(n), Traversed once with a length of n Array of
Spatial complexity ：O(n), Set up an array auxiliary

3、 ... and 、 Minimum cost of climbing stairs

solution : Dynamic programming

• You can use an array to record every time you climb to the i Minimum cost of stairs , Then the state will be transferred once every step is added , The final result .
• The initial state ） Because it can be directly from the 0 Grade or grade 1 The steps begin , Therefore, the cost of these two levels is directly 0.
• State shift ） One step at a time , There are only two cases , Or it takes a step up the front step , Or two steps up the first two steps , Because of the cost on the front steps, we all got , Therefore, the minimum value can be updated every time , The transfer equation is dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

class Solution {
    
public:
    int minCostClimbingStairs(vector<int>& cost) {
    
        //dp[i] It means to climb to the first i The minimum cost of stairs 
        vector<int> dp(cost.size() + 1, 0); 
        for(int i = 2; i <= cost.size(); i++)
            // Choose the smallest plan each time 
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 
        return dp[cost.size()];
    }
};

Time complexity ：O(n), among n For the given array length , Traversing the array once
Spatial complexity ：O(n), Auxiliary array dp Space