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不是很大的话,我们还可以使用公式来算,他的通项公式如下
长按上图,识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"赞"吧