509. 斐波那契数 JavaScript实现

509. 斐波那契数

题目链接

一、动态规划

1、确定dp数组的含义
dp[i]代表第i个数的斐波那契数，dp是一个长度为n的数组，需要把每个数对应的斐波那契数存进去。
2、状态转移方程
F(n) = F(n - 1) + F(n - 2)
3、初始化dp数组
F(0) = 0，F(1) = 1
4、遍历顺序
dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，所以遍历顺序是从前往后

二、代码实现

var fib = function(n) {
    // 1、定义dp数组，数组是一个长为n的数组，用来存放0-n之间每个数的斐波那契数
    let dp = new Array(n);

    // 2、初始化
    dp[0] = 0,dp[1] = 1;

    // 3、开始从前往后遍历
    for(let i=2;i<=n;i++){
        // 状态转移方程
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 返回的是第n个数的结果
    return dp[n];
};