On this page

斐波那契数

TIP

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

js

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

思路

递归做法

js

var fib = function(n) {
    if(n===0) return 0
    if(n===1 || n===2) return 1
    if(n>1)
    return fib(n-1)+fib(n-2)
};

动规五部曲

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

js

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