LeetCode70 — Climb the stairs

Topic describes

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: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

Train of thought

Climb one or two steps at a time. So when we climb four steps, the number of ways we can climb three steps, plus the number of ways we can climb two steps, is equal to F of 3 plus F of 2 is equal to 3 plus 2 is equal to 5. So when we climb N steps, we have F of N minus 1 plus F of N minus 2 ways.

The solution

Plan 1: Brute force cracking

We can recursively get all the ways that are less than N and add them up to get the result. The end of the recursion is marked by N=1 or N= 2.

var climbStairs = function(n) {
    if (n == 1) return 1
    if (n == 2) return 2
    return climbStairs(n - 1) + climbStairs(n - 2)};Copy the code

Time complexity O(). This kind of brute force solution is going to run out of time, which is obviously not what we want.

Plan two: optimize brute force cracking

From the previous method, we can find that the results of each step are repeated. For example, F(6) plus F(5) is going to compute F(5) plus F(4), and F(5) we’ve already done that, so let’s not double compute it. So we can use an array to store the results for easy reuse.

var climbStairs = function(n) {
    let arr = []
    function climb(n) {
        if (n == 1) return 1
        if (n == 2) return 2
        if (arr[n] > 0) return arr[n]
        
        arr[n] = climb(n - 1) + climb(n - 2)
        return arr[n]
    }
    return climb(n)
};
Copy the code

Time complexity O(n), after optimization to improve the speed, will not exceed the time limit.

Plan three: problem decomposition

It’s the same idea as recursion, breaking up a big problem into smaller problems, only this time we use a loop to reduce memory overhead.

var climbStairs = function(n) {
    if (n == 1) return 1
    if (n == 2) return 2

    let arr = []
    arr[1] = 1
    arr[2] = 2
    for (let i = 3; i<= n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2]}return arr[n]
};
Copy the code

Time complexity O(n), optimized memory consumption, speed does not improve.

Scheme 4: Fibonacci number

We saw from the last scheme that this is a Fibonacci sequence.

var climbStairs = function(n) {
    if (n == 1) return 1
    if (n == 2) return 2
    
    let first = 1
    let second = 2
    for (let i = 3; i<= n; i++) {
        let third = first + second
        first = second
        second = third
    }
    return second
};
Copy the code

Time complexity O(n)