首页 > 代码库 > LeetCode:Climbing Stairs

LeetCode: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?

思路:斐波那契数列的应用。

f(n)=f(n-1)+f(n-2)。当中f(1)=1,f(2)=2。此题假设用递归会超时,所以採用非递归的方法求斐波那契数列的第n项。


代码:

int Solution::climbStairs(int n)
{
    int n1 = 1;
    int n2 = 2;
    if(n == 1)
        return 1;
    if(n == 2)
        return 2;
    while(n > 2)
    {
        int temp = n1;
        n1 = n2;
        n2 = n2 + temp;
        n--;
    }
    return n2;
}


LeetCode:Climbing Stairs