题目：一只青蛙一次可以跳1级台阶，也可以跳2级台阶。请问该青蛙跳上一个n级台阶总共有多少种跳法。

分析：我们把n级台阶时的跳法看成是n的函数f(n)，当n>2时，第一次跳的时候有两种选择，第一次跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即f(n-1)；另外一种是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即f(n-2)。这样不难看出总跳法的数目f(n)=f(n-1)+f(n-2)；f(1)=1，f(0)=0。这样就变成了斐波那契数列的求解。我们可以用递归直接实现如下:

long long Fibonacci(unsigned int n){    if(n<=0)        return 0;    if(n=1)        return 1;    return Fibonacci(n-1)+Fibonacci(n-2);}

但是问题来了：上述递归算法有很严重的效率问题。时间复杂度是以n的指数方式递增的。因此实际软件开发中是不会用此方法的。

由于上面的递归过程中有很多重复计算，所以只要除去这些重复计算我们的算法就会大大的优化。更简单的方法是从下往上计算，首先根据f(0)和f(1)计算出f(2)，在根据f(1)和f(2)计算出f(3)...一次类推就会计算出f(n)，时间复杂度是O(n).实现如下：

long long Fibonacci(unsigned int n){    int result[2]={0,1};    if(n<2)        return result[n];        long long fibNMinusOne=1;    long long fibNMinusTwo=0;    long long fibN=0;    for(unsigned int i=2;i<=n;i++)    {        fibN=fibNMinusOne+fibNMinusTwo;        fibNMinusTwo=fibNMinusOne;        fibNMinusOne=fibN;    }    return fibN;}