剑指 Offer 10 - I. 斐波那契数列

题目描述 (opens new window)

解题方案

• 标签：动态规划

• 本题是经典的动态规划问题，围绕斐波那契数列方程 F(n+1) = F(n) + F(n−1) 进行解题，所以在求 n+1 元素时，只需要知道第 n 和 n-1 个元素即可。

  • 状态定义：F[n] 表示的含义为斐波那契数列中第 n 个数字
  • 转移方程：F(n+1) = F(n) + F(n−1)，所以在求 n+1 元素时，只需要知道第 n 和 n-1 个元素即可，故而运算过程中不需要保存数组
  • 初始状态： F[0] = 0, F[1] = 1 ，因为在计算 n+1 时需要 2 个元素，所以要初始化 2 个值；

• 其中取模 1000000007 运算主要是为了避免数字溢出，这步运算在每次计算出新的斐波那契数时进行即可，因为模运算的特性，后续再进行加法运算也不会有任何影响

  • 模运算特性：(x + y) % z = ((x % z) + (y % z)) % z

• 时间复杂度：O(n)，空间复杂度：O(1)

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
  let n1 = 0, n2 = 1, sum;
  for(let i = 0; i < n; i++){
    sum = (n1 + n2) % 1000000007;
    n1 = n2;
    n2 = sum;
  }
  return n1;
};

这道题目还可以使用递归的方式解决：

• 原理: 原理： 把 f(n) 问题的计算拆分成 f(n-1) 和 f(n-2) 两个子问题的计算，并递归，以 f(0)和 f(1) 为终止条件。
• 缺点: 大量重复的递归计算，例如 f(n) 和 f(n - 1) 两者向下递归需要 各自计算 f(n−2) 的值。

记忆化搜索：

• 原理：在递归法的基础上，新建一个长度为n的数组，用于在递归时候存储f(0)和f(n)数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。
• 缺点：记忆化搜素需要额外的O(n)空间复杂度

/**
 * @param {number} n
 * @return {number}
 */
let memo = [];
var fib = function (n) {
  if (n === 0) {
    return 0
  }
  if (n === 1) {
    return 1
  }
  // 如果memo[n] 存在的话
  if (!memo[n]) {
    memo[n] = (fib(n - 1) + fib(n - 2)) %  1000000007;
  } 
  return memo[n]
};