题目
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n，请计算 F(n) 。
题解
暴力递归，存在大量重复计算，不明白的往下翻看一下下面的干货题解就行了。
var fib = function (N) {
if (N == 0) return 0;
if (N == 1) return 1;
return fib(N - 1) + fib(N - 2);
};
降维打击，解决重复计算问题，不明白的往下翻看一下下面的干货题解就行了。
/**
* @param {number} N
* @return {number}
*/
var fib = function (N) {
var dp = [0, 1, 1];
for (var i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
};
再次降维，优化，不明白的往下翻看一下下面的干货题解就行了。
var fib = function (N) {
if (N == 0) return 0;
if (N == 2 || N == 1) return 1;
var prev = 1,
curr = 1;
for (var i = 3; i <= N; i++) {
var sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
};
后记
本文的代码摘自 - js 数据结构 - 链表 JS 中的算法与数据结构——链表 (Linked-list) 数据结构：链表