一、题目内容 简单
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给你 n ,请计算 F(n)
示例1:
输入:2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例2:
输入:3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例3:
输入:4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3
二、解题思路
动规五部曲:
这里我们要用一个一维 dp 数组 来保存递归的结果
- 确定 dp 数组 以及下标的含义
dp[i]
的定义为:第 i 个数的斐波那契数值是dp[i]
- 确定递推公式
题目已经把递推公式直接给我们了:状态转移方程 **dp[i] = dp[i - 1] + dp[i - 2]**
- dp 数组 如何初始化
题目中把如何初始化也直接给我们了,如下
dp[0] = 0;
dp[1] = 1;
- 确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2]
中可以看出,dp[i]
是依赖dp[i - 1]
和 dp[i - 2]
,那么遍历的顺序一定是从前到后遍历的
- 举例推导 dp 数组
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]
,我们来推导一下,当 N 为 10 的时候,dp 数组 应该是这样的数列:0 1 1 2 3 5 8 13 21 34 55
。用来检验代码的正确性
三、具体代码
/**
* @param {number} n
* @return {number}
*/
var fib = function (n) {
if (n < 2) return n;
const dp = [0, 1]; // 初始化序列
// 按顺序遍历,递推
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
/**
* 时间复杂度:O(n)
* 空间复杂度:O(n)
*/
当然可以发现,我们只需要维护两个数值就可以了,不需要记录整个序列
/**
* @param {number} n
* @return {number}
*/
var fib = function (n) {
if (n < 2) return n;
let dp0 = 0, dp1 = 1, i = 2, res = 0;
for (; i <= n; i++) {
res = dp0 + dp1;
dp0 = dp1;
dp1 = res;
}
return res;
};
/**
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
四、其他解法
递归解法
/**
* @param {number} n
* @return {number}
*/
var fib = function (n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
};
/**
* 时间复杂度:O(2^n)
* 空间复杂度:O(n)
*/