首页 > itarticle > 70. climbing stairs

70. climbing stairs

admin 11月 12, 2020 0

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

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

假设有n个阶梯，爬到n有2种方法：

从n-1处爬到n
从n-2处爬到n。

一. 符合递归思想。当n太大的时候，递归层数太多，栈溢出。

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

二. 菲波那切数列

class Solution {
public:
    int (int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        
        int fir = 1;
        int sec = 2;
        int num = 0;
        for (int i = 3; i <= n; i++) {
            num = fir + sec;
            fir = sec;
            sec = num;
        }
        return num;
    }
};