题目：写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下：

1503419-20190728160033362-1867691124.png

书中方法一：递归

1503419-20190728160255858-1628823257.png

我们不难发现在这颗树中有很多的节点是重复的，而且重复的节点数会随着n的增大而急剧增加，这意味着计算量会随着n的增大而急剧增大。事实上，用递归的方法计算的时间复杂度是以n的指数的方式递增的。

这种方法效率不高，因为可能会有很多重复计算。

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

书中方法二：

更好的方法是将这个斐波那契数列的计算理解成动态规划，第n步的结果依赖于第n-1步和第n-2步的结果，状态转移方程很容易写出来。

    public long calculate2(int n){
        if(n <= 0)return 0;
        if(n == 1)return 1;
        long preLast = 0;
        long last = 1;
        long result = 0;
        
        for(int i=2; i<=n; i++){
            result = preLast + last;
            preLast = last;
            last = result;
        }
        
        return result;
    }

扩展：青蛙跳阶

一次可以跳1阶或2阶，问跳上n阶台阶有多少种跳法。

依旧可以利用动态规划的思想，第m阶的跳法总数 可由 第m-1阶的跳法总数加上第m-2阶的跳法总数 得到。从头开始遍历到n就可以求出第n阶的跳法总数。

参考

《剑指offer》面试题9 斐波那契数列 Java版