509 斐波那契数

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。

题解

斐波那契数列主要是要讲动态规划的五部曲。

确定dp数组以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推倒dp数组

那我们对此题进行一下分析，首先，dp数组的含义和下标的含义。

一，dp[i]表示第i个斐波那契数，i表示第几个数
二，递推公式，题目中已经给我们 dp[i] = dp[i-1] + dp[i-2]
三，dp数组初始化，题目中也给了我们 i=0, dp[0] = 0, i=1, dp[1] = 1
四，确定遍历顺序，从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
五，dp[2] = dp[0] + dp[1] = 1

综合来看：

javascript

var fib = function(n) {
    var dp = [0, 1]
    if(n == 0 || n === 1) {
        return dp[n]
    }
    for(let i=2;i<=n;i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

509 斐波那契数 ​

题解 ​

509 斐波那契数

题解