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) 。

题解

暴力递归，存在大量重复计算，不明白的往下翻看一下下面的干货题解就行了。

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;
};

干货题解

官方题解 动态规划套路详解 题解 - 上面的代码就是这儿抄的