【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?

解题思路：这是一道斐波拉契数列题。看到斐波那契数列就自然想到利用递归，然而在这里递归的效率非常低，荣誉计算的数量增长的非常快，直接导致出现TLE（Time Limit Exceeded）错误。这是因为在递归的时候许多值被重复计算了多次，根据《C和指针》上对斐波那契数列的介绍，在n=30时，Fibonacci(3)的值被计算了317811次。这是非常可怕的，因此我又采用迭代的思路写了一组代码。迭代的思路也比较简单，设定初始f(1)和f(2)的值，在每次迭代中将前两次的计算结果相加作为本次计算结果即可。下面给出递归代码和迭代代码。

递归代码（出现超时错误）：

class Solution {
public:
    int climbStairs(int n) {
        int CurrChoices;
        if(n==0){
            CurrChoices=1;
        }else if(n==1){
            CurrChoices=climbStairs(n-1);
        }else{
            CurrChoices=climbStairs(n-1)+climbStairs(n-2);
        }
        return CurrChoices;
    }
};

迭代代码：

class Solution {
public:
    int climbStairs(int n) {
        int CurrChoice,OlderChoice,OldestChoice;
        CurrChoice=OlderChoice=OldestChoice=1;
        if(n==0)return 1;
        if(n==1)return 1;
        while(n>1){
            n-=1;
            OldestChoice=OlderChoice;
            OlderChoice=CurrChoice;
            CurrChoice=OlderChoice+OldestChoice;
        }
        return CurrChoice;
    }
};

【Leetcode】Climbing Stairs,布布扣,bubuko.com

【Leetcode】Climbing Stairs

原文：http://blog.csdn.net/ussam/article/details/21620817