07-斐波那契-动态规划

题目描述

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

代码

function Fibonacci(n)
{
    // write code here
    if(n<1) return 0;
    if(n<=2) return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
}

说明

未跑过

image.png image.png

更好的办法

该题更好的方法是采用动态规划来做。
动态规划讲解

代码

function Fibonacci(n)
{
   if(n==0) return 0;
   let last = 0;
   let nextLast = 1;
   let res = 1;
   
   for(let i=1;i<n;i++){
       res = last+nextLast;
       last = nextLast;
       nextLast = res;
   }
    return res;
}

采用动态规划更快