动态规划：斐波那契数列

我只是一个头图

问：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

---

斐波那契数列简单介绍

image

我的解法：

 public static int Fibonacci(int n) {
        if(n <= 1){
            return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }

my.png

注：从Fibonacci(n-1)+Fibonacci(n-2)明显看出使用的是递归，此题用递归两三行代码即可搞定。但是，若出题者准备着一个超大的n，那么很有可能会 Stack Overflow（递归的本质就是栈），为什么会栈溢出？因为重复计算，举个栗子：

当n=4时，

Fibonacci(4) = Fibonacci(3) + Fibonacci(2)

​ = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0)

​ = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果，对于程序来说它每次递归都是未知的，因此光是n=4时Fibonacci(1)就重复计算了3次之多。

其他解法：

public int Fibonacci(int n) {
        int preNum=1;
        int prePreNum=0;
        int result=0;
        if(n<=1)
            return n;
        for(int i=2;i<=n;i++){
            result=preNum+prePreNum;
            prePreNum=preNum;
            preNum=result;
        }
        return result;
 
    }

Snipaste_2019-02-09_20-54-33.png

注：<font color="blue">动态规划</font>（Dynamic Programming）。

动态规划简单介绍：https://blog.csdn.net/u013309870/article/details/75193592

动态规划算法也可以说是 '记住求过的解来节省时间';

动态规划算法的核心就是记住已经解决过的子问题的解。

上述代码需要用到三个数进行操作（preNum、prePreNum、result），实际上可以简化为两个数，从而节省空间，代码如下：

 public static int Fibonacci(int n) {
        int pre = 0, next = 1;
        while(n-->0) {
            next += pre;
            pre = next - pre;
        }
        return pre;
    }

---