首页 > 代码库 > Leetcode:Climbing Stairs 斐波那契数

Leetcode:Climbing Stairs 斐波那契数

2024-07-04 12:14:34   226人阅读

戳我去解题

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层有f(n)中走法，因为每次只能走1步或2步，则 f(n) = f(n-1) + f(n-2)

很明显是一个斐波那契数，f(0) = 0, f(1) = 1  

1. 递归，  f(n) = f(n-1) + f(n-2) 很容易想到递归，但是递归过程中存在大量的重复计算，会超时

2. 迭代

class Solution {
public:
    int climbStairs(int n) {
        assert(n >= 0);
        int prevTwo = 0;
        int prevOne = 1;
        int cur = 1;
        for (int i = 1; i <= n; ++i) {
            prevOne = cur;
            cur = prevOne + prevTwo;
            prevTwo = prevOne;
        }
        return cur;
    }
};

 

3. 直接计算：

斐波那契直接可以计算出表达数出来，且计算方法有好几种：等比数列法、矩阵法、生成函数法

具体见：斐波那契解法

class Solution {
public:
    int climbStairs(int n) {
        assert(n >= 0);
        double s = sqrt(5);
        return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1)) / s + 0.5);
    }
};

 


联系
我们