10. 斐波那契数列

来源

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例:

示例 1.

输入：n = 2
输出：1

示例 2.

输入：n = 5
输出：5

提示：

• 0 <= n <= 100

思路

斐波那契数列 f(n) = f(n-1) + f(n-2) 最简单的解法是

const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));

           10
          /   \
         9     8
       /  \   /  \
      8   7   7   6
     / \ / \ / \  / \
    7  8 6 5 6 5  5 4

这样时间复杂度是 O(n²)，随着 n 越大递归的速度就越慢，有越来越多重复的计算。

我们反过来，发现规律是每行的结果，都是用之前的的两个结果相加，这样就没有重复的计算了。

f(2) = f(1) + f(0)
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
...
f(n) = f(n-1) + f(n-2)

           10
          /
         9
       /  \
      8   7
     / \ / \
    7  8 6 5

我们得到了时间复杂度为 O(logn) 的解法，

解题

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n <= 1) return n;
  let a = 0;
  let b = 1;
  let x = 1000000007; // 题目要求
  let res = 0;
  for (var i = 2; i <= n; i++) {
    res = a + b;
    res = res <= x ? res : res % x; // 题目要求
    a = b;
    b = res;
  }
  return res;
};

题目 2

青蛙跳台阶问题

题目

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n  级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例:

示例 1.

输入：n = 2
输出：2

示例 2.

输入：n = 7
输出：21

提示：

• 0 <= n <= 100

思路

稍微分析一下，此题跟斐波那契数列几乎一样，除了 f(0) = 1，把上题稍微修改一下即可。

解题

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function (n) {
  if (n <= 1) return 1;
  let a = 1;
  let b = 1;
  let x = 1000000007; // 题目要求
  let res = 0;
  for (var i = 2; i <= n; i++) {
    res = a + b;
    res = res <= x ? res : res % x; // 题目要求
    a = b;
    b = res;
  }
  return res;
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch