首页 > itarticle > leetcode-70-climbing stairs

leetcode-70-climbing stairs

admin 11月 12, 2020 0

题目

爬梯子，梯子共有n阶，每次你可以攀登1阶或者2阶，从梯子底端爬至顶端，会有多少种不同的方案

分析

递归实现，最后一步一定是走了1阶或者两阶，所以f(n) = f(n-1)+f(n-2)
注:直接调用递归会超时

C++代码实现

class Solution {
public:
    int (int n) {
        if(n <= 2) return n;
        else return res(n);

    }
    
    int res(int n){
        int a[n+1];
        a[1] = 1;
        a[2] = 2;
        for(int i = 3; i <= n; i++)
          a[i] = a[i-2] + a[i-1];
        return a[n];
    }
};