首页 > 代码库 > leetcode 刷题之路 92 Climbing Stairs

leetcode 刷题之路 92 Climbing Stairs

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级,如果一次可以跳1级,也可以跳2级,求总共有多少总跳法。

分析:

一次最多只能跳两级,那么对于第n级(n>=2)台阶,显然只能从第n-1级跳一级到达或者从第n-2级跳两级到达,因此只要知道了n-1级和n-2级的跳法个数,求和就是第n级的跳法个数。

设跳法个数为f(n),n为台阶级数,则有:

f(n)=f(n-1)+f(n-2),

当n=0,1时,f(n)=1

题目转换成一个典型的Fibonacci序列问题。

Accepted Solution:

class Solution {
public:
    int climbStairs(int n) 
    {
        int first=1,second=1;
        for(int i=2;i<=n;i++)
        {
            int temp=second;
            second=first+second;
            first=temp;
        }
        return second;
    }
};