509. Fibonacci number, all paths of climbing stairs, minimum cost of climbing stairs

509. Fibonacci number

Fibonacci number （ Usually use F(n) Express ） The sequence formed is called Fibonacci sequence . The sequence is composed of 0 and 1 Start , Each of the following numbers is the sum of the first two numbers . That is to say ：
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2), among n > 1
Given n , Please calculate F(n) .

Input ：n = 2
Output ：1
explain ：F(2) = F(1) + F(0) = 1 + 0 = 1

Input ：4
Output ：3
explain ：F(4) = F(3) + F(2) = 2 + 1 = 3

Here you are 4,4 Is the need to 3 and 2,3 need 2 and 1,2 need 1 and 1

from 1 Traverse to this number Save the traversal value with an array

class Solution {
    
public:
    int fib(int n) {
    
     if(n<=1) return n;
     vector<int> temp(n+1);
     temp[0]=0;
     temp[1]=1;
     for(int i=2;i<=n;i++){
    
        temp[i]=temp[i-1]+temp[i-2];
     }
     return temp[n];
    }
};

No maintenance from 1 To n The whole number , Save with two values

class Solution {
    
public:
    int fib(int n) {
    
     if(n<=1) return n;
     vector<int> temp(2);
     temp[0]=0;
     temp[1]=1;
     for(int i=2;i<=n;i++){
    
        temp[i%2]=temp[(i-1)%2]+temp[(i-2)%2];
     }
     return temp[n%2];
    }
};

recursively

The end point is to return 1 and 0

class Solution {
    
public:
    int fib(int n) {
    
     if(n<=1) return n;
     return fib(n-1)+fib(n-2);
    }
};

70. climb stairs

Suppose you're climbing the stairs . need n You can reach the top of the building .

Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？
Input ：n = 3
Output ：3
explain ： There are three ways to climb to the top .

1. 1 rank + 1 rank + 1 rank
2. 1 rank + 2 rank
3. 2 rank + 1 rank

Determine the recurrence formula （ Dynamic programming ）

1、 determine dp The meaning and recursion of array and subscript

dp[i]=dp[i-1]+dp[i-2];

Indicates that climbing to the current layer has the addition of two methods from the next layer and the lower layer
2、dp Array initialization

dp[1]=1;
dp[2]=2;

3、 Determine the order of traversal
Iterative approach Save from front to back with an array
recursively From back to front , But it was also calculated before

1、 Iterative approach , Save with array （ Dynamic programming ）

class Solution {
    
public:
    int climbStairs(int n) {
    
        if(n<=2) return n;
        vector<int>dp(n+1);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
    
            dp[i]=dp[i-1]+dp[i-2];

        }
        return dp[n];
    }
};

2、 No maintenance from 1 To n The whole number , Save with two values （ Dynamic programming ）

class Solution {
    
public:
    int climbStairs(int n) {
    
        if(n<=2) return n;
        vector<int>dp(n+1);
        dp[0]=2;
        dp[1]=1;
        for(int i=3;i<=n;i++)
        {
    
            dp[i%2]=dp[(i-1)%2]+dp[(i-2)%2];

        }
        return dp[n%2];
    }
};

3、 recursively （ Dynamic programming ）

class Solution {
    
public:
    int climbStairs(int n) {
    
        if(n<=2) return n;
        return climbStairs(n-1)+ climbStairs(n-2);
    }
};

4、 backtracking

The following code result is correct , It has been running on my computer for nearly 15 seconds , But using other code only takes a few seconds .

class Solution {
    
public:
    int climbStairs(int n) {
    
        int count = 0;
        dfs(n, 0, count);
        return count;
    }
    int dfs(int n, int index, int& count) {
    
        if (n == index)count++;
        if (index > n) return -1;
        // You can choose to climb one step in the current state , You can also choose to climb two steps 
        // Take a step 
        dfs(n, index + 1, count);
        // Climb two steps 
        dfs(n, index + 2, count);
        return -1;
    }
};

5、 The reasons for the timeout of recursion and backtracking

Recursion appeared A lot of double counting , For example, I climb 10 layer , As shown in the figure below, there are two branches , One is direct 8 layer , One is from 9 The layer continues to 8 layer , There will be a lot of overlap . If the recursive tree continues to draw down , There will be more overlap , Recursive method calculates a large number of overlapping sub problems, which leads to low efficiency .

The same goes for backtracking , At this time, I am on the first floor of the stairs , Many branches will pass through me , But when the first branch passes through, I have calculated how many ways from me to the vertex , But the rest of the branches passed by me, and I even repeated the calculation , This creates waste .

resolvent ： Add a global container , Store information
For backtracking .

class Solution {
    
public:
    vector<int>memo;
    int climbStairs(int n) {
    
        int count = 0;
        memo = vector<int>(n + 1, -1);
        dfs(n, 0, count);
        return count;
    }
    int dfs(int n, int index, int& count) {
    
        if (n == index) {
     count++; return -1; }
        if (index > n) return -1;
        if (memo[index] != -1) {
     count += memo[index]; return -1; }

        int temp = count;

        // You can choose to climb one step in the current state , You can also choose to climb two steps 
        // Take a step 
        dfs(n, index + 1, count);
        // Climb two steps 
        dfs(n, index + 2, count);
        memo[index] = count - temp;
        return -1;

    }
};

class Solution {
    
public:
    vector<int>memo;
    int climbStairs(int n) {
    
        memo = vector<int>(n + 1, -1);
       return  dfs(n);
    }
    int dfs(int n) {
    
        if (n <= 2) return n;
        if (memo[n] != -1) return memo[n];

        int count= dfs(n - 1)+ dfs(n - 2);
        memo[n] = count;
        return count;
    
    }
};

746. Use the minimum cost to climb the stairs

Give you an array of integers cost , among cost[i] It's from the stairs i The cost of climbing a step up . Once you pay this fee , You can choose to climb up one or two steps .

You can choose from the subscript to 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 .

Input ：cost = [1,100,1,1,1,100,1,1,100,1]
Output ：6
explain ： You will subscript 0 The steps begin .

• payment 1 , Climb up two steps , The arrival subscript is 2 The steps of .
• payment 1 , Climb up two steps , The arrival subscript is 4 The steps of .
• payment 1 , Climb up two steps , The arrival subscript is 6 The steps of .
• payment 1 , Climb up a step , The arrival subscript is 7 The steps of .
• payment 1 , Climb up two steps , The arrival subscript is 9 The steps of .
• payment 1 , Climb up a step , Get to the top of the stairs .
  The total cost is 6 .

Determine the recurrence formula

1、dp The meaning of arrays and subscripts
dp[i] It means to arrive at the third i The minimum cost of layers
2、 Determine the recurrence formula
arrive i There are two ways to layer , One is dp[i-1], One is dp[i-2], Then choose the smallest

dp[i]=min{
    dp[i-1],dp[i-2]}+cost[i];

Why cost[i], Because the title means up to i Need those physical strength , Therefore, you should spend your physical strength wherever you go
3、dp Array initialization
dp[0] = cost[0];
dp[1] = cost[1];
4、 Determine the order of traversal
It's OK to traverse from front to back

Code

class Solution {
    
public:
    int minCostClimbingStairs(vector<int>& cost) {
    
        vector<int>dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i <cost.size(); i++) {
    
          dp[i] = min(dp[i - 1],dp[i - 2] ) + cost[i];
        }
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};