Updated : 4月 05, 2019 in 题解

70. Climbing Stairs

源链接: https://leetcode.com/problems/climbing-stairs

题目描述:每次走楼梯可以走一台或者两台,问走上n层台阶有多少种走法?

分析:

设走上n层楼梯共有F(n)中走法,则在最后一步到最高的n层分为两种情况:
1.从n-1层楼梯走了一台上来
2.从n-2层楼梯走了两层
所以对于上n层楼梯的走法是上述的两种走法之和,即F(n-1) + F(n-2)
对于n=1的情况,显然只有一种走法, 对于n=2的情况,有两种
现在看来,n层楼梯的走法刚好就是一个斐波那契数列的第n-1项,所以很容有写出如下的

代码:

class Solution {
public:
    int climbStairs(int n) {
        if ( n == 1) {
            return 1;
        }
        int res = 2;
        int i = 2, last = 1, tmp;
        while ( i++ < n) {
            tmp = res;
            res += last;
            last = tmp;
        }
        return res;
    }

};

发表评论