LeetCode(509)斐波那契数

今天是小呆刷题的第10天，今天的题目是：力扣（LeetCode)的第509题，斐波那契数

题目要求

斐波那契数（通常用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
3

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

提示：

0 <= n <= 30

解题思路

大名鼎鼎的斐波那契数，也是面试中经常会考的一道算法题。这道题的解法有很多种，最简单的就是使用递归。毕竟怎么写题目要求都已经给出来了，所以很快就能写出来一个解法：

n < 2，返回n
F(n) = F(n - 1) + F(n - 2)

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n < 2) return n
    return fib(n - 1) + fib(n - 2)
};

但是这样就完了吗？其实并没有。因为按照小呆的经验判断，这个解法一定不是面试官想要的答案。所以它的性能问题出在哪了呢？然后我发现，由于F(n) = F(n - 1) + F(n - 2)，所以当n的值越大，递归的次数就越多，就会出现重复的计算，如下图：

递归的性能问题

在F(5) = F(4) + F(3)中，计算过一次F3的值，用蓝色表示
但是在F(4) = F(3) + F(2)中，又计算了一次F3的值，用红色表示
N越大，重复计算的次数就越多

问题发现了，但是怎么优化呢？还是看上图（更形象），如果我把每次的值都存起来，是不是就不用重复计算了呢？

根据F(0), F(1), 可以推断出F(2)，我们把每次的值都存起来。
根据F(2), F(1), 可以推断出F(3)，因为值存起来了，所以可以直接用，避免了再次计算已推断出的值
最后一次存的值，其实就是F(n) = F(n - 1) + F(n - 2)

我们可以用一个数组，下标表示n，值表示F(n)。这样就可以不用递归解出来这道题，依旧老规矩，一张动图辅助理解：

动态规划-斐波那契数

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let dp = [0, 1]
    for(let i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2]
    }
  	return dp[n]
};