斐波那契数列，跳台阶(dp思想)

一 . 斐波那契数列：1，1，2，3，5，8，13，21

即后一项是前两项的和。

class Solution {
private:
    int arry[50];
public:
    Solution() {
        memset(arry, 0, sizeof(0));
        arry[1] = arry[2] = 1;
        for(int i = 3; i <= 39; i ++) arry[i] = arry[i - 1] + arry[i - 2];
    }
    int Fibonacci(int n) {
        return arry[n];
    }
};

递归方式：

int Fibonacci(int n)
{
    if(n == 1 || n == 2 )
        return 1;
    else
        return Fibonacci(n-1)+Fibonacci(n-2);
}

二 . 跳台阶：

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

青蛙的最后一步可能是1个台阶，也可能是两个台阶。所以F(n) = F(n-1) + F(n-2)；

    int jumpFloor(int number) {
        int arry[number + 5];
        arry[1] = 1; arry[2] = 2;
        for(int i = 3; i <= number; i++) arry[i] = arry[i-1] + arry[i-2];
        return arry[number];
    }

三 . 变态跳台阶：

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

f(n) = f(0)+f(1)+f(2)+f(3)+......+f(n-1);

　　　1      1     2      4

规律为：2⁰+2¹+.....+2ⁿ    结果为 2ⁿ⁺¹-1

所以最终结果为1+2^n-1-1 = 2^n-1 ；

其实就是2^n-1,下面使用一下前两天学的快速幂

    int jumpFloorII(int number) {
        int n = 1;
        int base = 2;
        number -= 1;
        while(number)
        {
            if(number & 1)
                n*=base;
            base *= base;
            number>>=1;
        }
        return n;
    }

求2的n-1次方的简便做法：

一行代码 return  1<<--number;