7.斐波那契数列

题目描述：

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

知识点：

• 动态规划
• 动态规划是把一个大的问题划分成一些重叠的小问题来解决，如斐波那切数列，爬楼梯等…..
• 分而治之是把一个大的问题分解成相互独立的小问题来解决，如翻转二叉树，判断一棵二叉树是否镜像等…..

解题思路：

• 这道题是一道考察动态规划的题，我们不断的累加求和便好值得注意的是，第0位为0，第1位为1
• 注意这道题我们可以减少时间复杂度，用两个指针一个临时变量来替代数组

解题代码：

• 数组

  function Fibonacci(n)
  {
    // write code here
    if(n === 0 || n ===1) return n;
    const res = [0,1];
    for(let i = 2;i<= n;i++) {
        res[i] = res[i-1] + res[i-2];
    }
    return res[res.length-1]
  }

• 指针

  function Fibonacci(n)
  {
    // write code here
    if(n === 0 || n ===1) return n;
    let dp1 = 0;
    let dp2 = 1;
    for(let i = 2;i<= n;i++) {
        let temp = dp2;
        dp2 = dp2 + dp1;
        dp1 = temp;
    }
    return dp2;
  }