在线题目链接：斐波那契数列

文章目录

1、题目描述

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

2、题目分析

有高中的数学知识，就应该知道斐波那契数列是这样的：1,1,2,3,5,8…

如果f(n)代表斐波那契数列第n项的值，那么：

既然我们已经可以得出公式了，那就很好写代码。最容易明白的就是递归了，上面的公式其实就是一个递归的公式。

下面提供多种解法：递归，动态规划，循环。

3、代码

3.1 递归方法

递归解法很简单：

3.11 Java代码

public class Solution {
    public int Fibonacci(int n) {
        //递归解法
        if(n<=1)return n;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

3.12 C++代码

class Solution {
public:
    int Fibonacci(int n) {
        //递归解法,超时
        if(n<=1)return n;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
};

我们都知道这种递归解法会有很多重复的计算，就像下面的，假设我们要计算f(10):

计算f(10)，要重复计算两次f（8），三次f（7），三次f（6），这种重复计算，对于数据比较大的时候，开销是非常大的。所以我们经常说，递归虽然好写，但是不建议在实现算法的时候使用递归算法。

3.2 动态规划

凡是能用递归写出的代码，一定能够用动态规划写出来。

我们知道递归是为了求某一个值，而必须先知道另外的几个值后才能求出来。而想要求那另外的几个值，还需要再求另外的另外的值，就像上面的递归二叉树，想要先求f（10），必须知道f（9）和f（8）。想要知道f（9）又得知道f（8）和f（7）…

上面递归是想要计算总体值，需要求局部的值，想要求局部的值，又要求局部的局部的值。

动态规划不是这样，动态规划是先从递归的终止条件开始计算，也就是说，动态规划先计算局部的值，然后根据局部的值的累积，最终得到整体要求的值。也就是与递归反过来了。

比如针对上面的求f（10），我们先求f（1），f（2），f（3）…最终肯定会求得f（10）。这样我们就没有进行重复的计算。每一项都是只计算一次。

看代码就能明白上面说的是什么意思了。下面的ret数组，ret[i]代表斐波那契数组的第i项。我们要求得第n项，最后求到ret[n]直接返回即可。

3.21 Java代码

public class Solution {
    public int Fibonacci(int n) {
       //动态规划
        if(n<=1)return n;
        int[] ret=new int[n+1];
        ret[0]=0;
        ret[1]=1;
        int i;
        for(i=2;i<=n;i++){
            ret[i]=ret[i-1]+ret[i-2];
        }
        return ret[n];
    }
}

3.22 C++代码

class Solution {
public:
    int Fibonacci(int n) {
        //动态规划
        //if(n<=1)return n;不知道这里为什么不能加这个
        int ret[n+1];
        ret[0]=0;
        ret[1]=1;
        int i;
        for(i=2;i<=n;i++){
            ret[i]=ret[i-1]+ret[i-2];
        }
        return ret[n];
    }
};

3.3 循环方法

所有的递归都可以写成动态规划，同理所有的动态规划，也一定能写成循环。只不过有的动态规划不好写成循环而已。本题是非常好写成循环的。

循环比动态规划好的原因在于，循环只用几个变量，循环使用它们得到最终结果，不保存之前的计算结果，动态规划却需要开辟一个数组，将所有计算过的结果保存，这很浪费空间。

3.31 Java代码

public class Solution {
    public int Fibonacci(int n) {
        //循环
        if(n<=1)return n;
        int ret=0;
        int r0=0,r1=1;
        int i;
        for(i=2;i<=n;i++){
            ret=r0+r1;
            r0=r1;
            r1=ret;
        }
        return ret;
    }
}

当然，上面使用三个变量，我们还可以再减少一个变量，使用两个变量：

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1)return n;
        int r1=0,r2=1,i;
        for(i=2;i<=n;i++){
            r2+=r1;
            r1=r2-r1;
        }
        return r2;
    }
}

3.32 C++代码

三个变量

class Solution {
public:
    int Fibonacci(int n) {
        //循环
        if(n<=1)return n;
        int ret=0;
        int r0=0,r1=1;
        int i;
        for(i=2;i<=n;i++){
            ret=r0+r1;
            r0=r1;
            r1=ret;
        }
        return ret;
    }
};

两个变量

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1)return n;
        int r1 = 0, r2 = 1,i;
        for(i=2;i<=n;i++){
            r2+=r1;
            r1=r2-r1;
        }
        return r2;
    }
};

4、总结

注意学会递归，动态规划，循环三者时间的关系

探讨学习加：
个人qq：1126137994
个人微信：liu1126137994