Leetcode - 70 - Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

Solutions:

(1) Applies to a small n

Try to compose the big abstract problem by similar small problems. Here, we can find that for n >= 3, f(n) = f(n-1) + f(n-2).

Caution, n>=3 in the loop we need to cover [2, n-1] or [3, n], namely (n-2) numbers.

To be faster than the recursion, we save the previous two data and update in the loop.

C++

class Solution {
public:
    int climbStairs(int n) {
        int ways = 0;
        if (n <= 0)
            return ways;
        if (n <= 2)
            return n;
        int pre1 = 2, pre2 = 1;
        for (int i = 2; i < n; i++) {
            ways = pre1 + pre2;
            pre2 = pre1;
            pre1 = ways;
        }
        return ways;
    }
};

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

// https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

Java:

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

// https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

(2) Fibonacci sequence equation

class Solution {
    public int climbStairs(int n) {
        double sqrt_5 = Math.sqrt(5);
        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
        return (int)(fib_n / sqrt_5);
    }
}

// https://leetcode-cn.com/problems/climbing-stairs/solution/hua-jie-suan-fa-70-pa-lou-ti-by-guanpengchn/