剑指offer10:斐波那契数列

题目一： 求斐波那契数列的第n项. 斐波那契数列公式：

$$f(0)=0$$ $$f(1)=1$$ $$f(n)=f(n-1) + f(n-2),n>1$$

对于斐波那契数列，学过程序语言的应该都知道. 教学时基本都是使用它来说明递归，导致一遇到这个问题的时候，一下就能反映过来，使用递归.

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

但是面试题这么就完了？ 😄，那是不可能的. 当我们把上诉代码展开时就会发现，出现了大量的重复计算，效率太低. 当不能递归时，一般从循环角度考虑，因为递归从上向下计算，导致出现重复计算，因此应该考虑从下往上计算，每个数字只计算一次.

int Fibonacci(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int f0 =0;
        int f1= 1;
        int fn= 0;
        for(int i=2; i<=n;i ++){
            fn = f0 + f1;
            //计算下一个数之前，更新fn-1和fn-2
            f0 = f1;
            f1 = fn;
        }
        return fn;
        }

题目二：台阶及类似问题，有一个n阶台阶，一次可以跳一阶或者二阶，问跳上一个n阶台阶共有多少种跳法。

假设当只有一个台阶时，那么只能跳一阶，当有两个台阶时，可以一次跳两阶或者跳两次. 当台阶有三阶时，跳到第三阶可能是从第二阶跳来，也可能是从第一阶跳来，则f(3)=f(2)+f(1).和斐波那契数列相同的递推公式. 换汤不换药,用递归思想分析问题，用循环实现.

题目三：变态跳台阶，一个n阶台阶，一次可以跳1次到n次，求跳上一个n阶台阶一共有多少种跳法. 假设当只有一个台阶时，那么只能跳一阶，当有两个台阶时，可以一次跳两阶或者跳两次. 当台阶有三阶时，跳到第三阶可能是从第二阶跳来，也可能是从第一阶跳来，也可能是直接跳到第三阶. 则f(3)=f(2)+f(1)+f(0). 同理，f(4)=f(3)+f(2)+f(1)+f(0). 每次将之前的所有结果求和.

class Solution {
public:
    int jumpFloorII(int number) {
    if(number==1)
        return 1;
    if(number==2)
        return 2;
    int sum=4, res=0;
    for(int i=3; i<=number;i++){
        res = sum;
        sum += res;
    }
    return res;
    }
};