1.题目

2.递归思路

最简单的就是递归（虽然效率低，时间复杂度高）
PS：其实我没写出来，我真的屑。T-T

var fib = function(n) {
    // 虽然递归都不配官方提起，但我连递归都不会写真的屑
    return n<=1?n:fib(n-1)+fib(n-2)
};

时间复杂度

大佬说画棵树看看，如下，可以看到这是一个完满（full）二叉树！
节点数就是时间复杂度

3.DP思路

动规五部曲：

1. 确定dp数组以及下标的含义

这里我们要用一个一维dp数组来保存递归的结果
dp[i]的定义为：第i个数的斐波那契数值是dp[i]

1. 确定递推公式

为什么这是一道非常简单的入门题目呢？
因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

1. dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
dp[1] = 1;

1. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55

var fib = function(n) {
    // 虽然递归都不配官方提起，但我连递归都不会写真的屑
    // return n<=1?n:fib(n-1)+fib(n-2)

    // DP写法，维度DP数组
    let dp=[0,1]
    for(let i=2;i<=n;i++){
        dp[i] =dp[i-1]+dp[i-2]
    }
    return dp[n]

};

3.1 优化空间的DP

只维护dp[0]和dp[1]

var fib = function(n) {
    // 虽然递归都不配官方提起，但我连递归都不会写真的屑
    // return n<=1?n:fib(n-1)+fib(n-2)

    // DP写法，只需要维护dp[0]和dp[1]两个数
    let dp=[0,1]
    let sum =0
    if(n<=1) return n
    for(let i=2;i<=n;i++){
        sum =dp[0]+dp[1]
        dp[0] =dp[1]
        dp[1] =sum
    }
    return dp[1]

};

空间复杂度就变成O（1）了

4. 尾递归优化

优化递归的函数调用栈，避免栈溢出，减少内存消耗。【如果可以自定义参数，就直接写myFib就好了】

var fib = function(n) {
    // 尾递归法
    if(n===0) return 0

    const myFib =function(n,ac1=0,ac2=1){
        if(n<=1) return ac2
        return myFib(n-1,ac2,ac1+ac2)
    }
    return myFib(n)
};