418，剑指 Offer-斐波那契数列

We don't get a chance to do that many things, and every one should be really excellent.

我们这一生能做的事情有限，所以要把每件事都做到完美。

问题描述

写一个函数，输入 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

递归解法

前面讲356，青蛙跳台阶相关问题的时候提到过斐波那契数列，代码比较简单

1public int fib(int n) {
2    if (n < 2)
3        return n;
4    return fib(n - 1) + fib(n - 2);
5}

当n很大的时候可能会出现数字溢出，所以我们需要用结果对1000000007求余，但实际上可能还没有执行到最后一步就已经溢出了，所以我们需要对每一步的计算都要对1000000007求余，代码如下

1int constant = 1000000007;
2
3public int fib(int n) {
4    if (n < 2)
5        return n;
6    int first = fib(n - 1) % constant;
7    int second = fib(n - 2) % constant;
8    return (first + second) % constant;
9}

之前讲过斐波那契数列递归的时候会造成大量的重复计算，比如就计算fib(6)为例来看下

我们看到上面相同颜色的都是重复计算，当n越大，重复的越多，所以我们可以使用一个map把计算过的值存起来，每次计算的时候先看map中有没有，如果有就表示计算过，直接从map中取，如果没有就先计算，计算完之后再把结果存到map中。

 1int constant = 1000000007;
 2
 3public int fib(int n) {
 4    return fib(n, new HashMap());
 5}
 6
 7public int fib(int n, Map<Integer, Integer> map) {
 8    if (n < 2)
 9        return n;
10    if (map.containsKey(n))
11        return map.get(n);
12    int first = fib(n - 1, map) % constant;
13    map.put(n - 1, first);
14    int second = fib(n - 2, map) % constant;
15    map.put(n - 2, second);
16    int res = (first + second) % constant;
17    map.put(n, res);
18    return res;
19}

非递归解法

我们还可以把斐波那契递归改为非递归，代码很简单，可以看下

 1public int fib(int n) {
 2    int constant = 1000000007;
 3    int first = 0;
 4    int second = 1;
 5    while (n-- > 0) {
 6        int temp = first + second;
 7        first = second % constant;
 8        second = temp % constant;
 9    }
10    return first;
11}

总结

斐波那契数列又称黄金分割数列，常见的比如兔子的繁殖，青蛙跳台阶等问题。递归方式解决是最容易理解的，但递归会包含大量的重复计算，效率很差，一般还是改为非递归为好。如果n不是很大的话，我们还可以使用公式来算，他的通项公式如下

●416，剑指 Offer-用两个栈实现队列

●410，剑指 Offer-从尾到头打印链表

●408，剑指 Offer-替换空格

●404，剑指 Offer-数组中重复的数字