这是一道动态规划经典例题,使用动态规划来解题。
dp[i]
含义:斐波那契数列的第i
个数为dp[i]
- 递推公式:根据定义易得:
dp[i] = dp[i - 1] + dp[i - 2]
- dp数组初始化:题目已经给出:
dp = [0, 1]
- 遍历顺序:根据定义,当前数依赖于前两个数,所以从前向后遍历
- 注意取模
(% 1000000007)
const fib = n => {
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
};