LeetCode daily Dynamic Planning: 70 stairs

The title information

Subject address: leetcode-cn.com/problems/cl…

Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1:

Input:2Output:2Explanation: There are two ways to climb to the top.1.  1Order +1 阶
2.  2 阶
Copy the code

Example 2:

Input:3Output:3Explanation: There are three ways to climb to the top.1.  1Order +1Order +1 阶
2.  1Order +2 阶
3.  2Order +1 阶
Copy the code

Idea 1: Fibonacci numbers

We can watch it and we can play with it a little bit

1. One step: Only one way to jump is to jump a space
2. Two steps: jump twice and jump once 2 steps
3. Three steps: 1+1+1, 2+1, 1+2
4. Four steps: 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2 (altogether five kinds)
5. Five steps 1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 1 + 2 + 1 + 1, 1 + 1 + 2 + 1, 2, 1 + 1 + 1 + 2 + 2 + 1, 2, 1 + 2 + 1 + 2 + 2 (eight)

And we get the rule that it’s a Fibonacci sequence, so the positive integers don’t start at the 0th point in the sequence and start at the first point

The Fibonacci sequence, which has a formula for calculating result directly from n.

Let’s pretend we don’t know the formula

We derived it iteratively:

Each time we record the new value through the first two items, and then iterate until we get to the NTH value we want. One spatial caveat here is that we don’t have to record the whole Fibonacci sequence, just two of them.

A code:

public int climbStairs(int n) {
    / / initial value
    if(n == 1) {return n;
    }
    int[] nums = {1.2};
    // The last value and the new value form a new binary array
    for(int i = 2; i < n; i++){
        int temp = nums[0] + nums[1];
        nums[0] = nums[1];
        nums[1] = temp;
    }
    return nums[1];
}
Copy the code

In general, it’s good. Time O(n), space O(1).

And then there’s the general formula solution, which goes without saying is optimal, but what we can’t ignore is the order logn of the square root. And the derivation of the Fibonacci state formula is in another paper

public int climbStairs(int n) {
    double sqrt5 = Math.sqrt(5);
    double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
    return (int) Math.round(fibn / sqrt5);
}
Copy the code

Idea 2: Dynamic planning

Because this is a very special problem, and actually the dynamic programming solution is already in the code but with a different focus. And I’m going to use this to get a feel for the idea of dynamic programming. Dp is a way of thinking about solving a new problem with a solution to a known problem. Recursion or iteration it’s just a way of writing code to implement this idea and whether we do space optimization or not it’s a way of thinking, it’s better to compress space. I’m not going to explore the concept in isolation here.

So the number of ways to get up the NTH stair, the number of ways to get up the NTH stair, is equal to the sum of the two parts.

Number of ways to climb n-1 stairs. Because one more step to get to the NTH

Number of ways to climb n-2 stairs. Because it takes two more steps to get to the NTH

So we get the formula

dp[n] = dp[n-1] + dp[n-2]
Copy the code

It also needs to be initialized

dp[0] =1
dp[1] =2
Copy the code

Time complexity: O(n)

Code 2:

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 2;
    for(int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n-1];
}
Copy the code

So there’s spatial optimization, you don’t need all of it to record the subproblems. I’m just going to slide the array and leave two of them

Code 3: Is the solution above solution 1

public int climbStairs(int n) {
    if(n == 1) return 1;
    int[] dp = {1.2};
    for(int i = 2; i < n; i++){
        int temp = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = temp;
    }
    return dp[1];
}
Copy the code

Well, we could of course write this recursively

Code 4:

public int climbStairs(int n) {
    // Recursive exit
    if(n == 1 || n == 2) {
        return n;
    }
    // Process and body
    return climbStairs(n-1) + climbStairs(n-2);
}
Copy the code

This thing is a problem to be solved in the test of time is also a timeout, repeated computation is we have to think in the dynamic programming problem, the front is a bottom-up so every time we record the new binary array in the future continue to be linear, top-down now such as the first layer and n – 2 n – 1 case calculation is repeated, we come to draw a diagram

First of all, it’s not linear, and it’s repeated on both sides, it’s 2n squared to the n2n, it’s one line and it’s done but it keeps recounting n long lines to become an n-level tree because they contain each other. So what we’re going to do is we’re going to save the subproblem, and then we’re going to take this instead of iterating.

Code 5:

public int climbStairs(int n) {
    int[] mind = new int[n+1];
    mind[0] = 1;
    mind[1] = 1;
    return recur(n,mind);
}
int recur(int n,int[] mind){
    // Recursive exit
    if(mind[n] ! =0) {return mind[n];
    }
    // Make recursive exits more than just initial values
    mind[n] = recur(n-1,mind) + recur(n-2,mind);
    return mind[n];
}
Copy the code

Now the time is order n.

conclusion

Ontology is a classic example of dynamic programming, and you can also transform the problem into solving the Fibonacci sequence so that you can focus on linear algebra. The complexity of the general term of the optimal solution is O(logn). There are a couple of interesting things about this problem. The derivation of the general term formula for the Fibonacci sequence is one of several examples that can be demonstrated after the fast powers of the number theory matrix have been added to the library.