美文网首页Java 杂谈算法和数据结构
动态规划:斐波那契数列

动态规划:斐波那契数列

作者: 就良同学 | 来源:发表于2019-02-09 21:21 被阅读16次
    我只是一个头图

    问:

    大家都知道斐波那契数列,现在要求输入一个整数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;
        }
    

    相关文章

      网友评论

        本文标题:动态规划:斐波那契数列

        本文链接:https://www.haomeiwen.com/subject/ilvzsqtx.html