我们先来看一下什么是斐波那契数列,这个应该在大一高数时大家都学过。

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)
——《百度百科》

具体函数表达参考下面这张图。

img
img

那么我们该如何求解与斐波那契数列相关的问题呢?

先看一下题目描述:

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

具体可以用以下几种方法求解:

使用递归

递归能将一个问题划分成多个子问题进行求解。求F(n)时会转化成求F(n-1)、F(n-2),以此类推,最后转化成几个F(0)、F(1)相加的结果。实现如下:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int Fibonacci(int n) {
int result = 0;
if (n <= 1){
return n;
}else{
result = Fibonacci(n - 1) + Fibonacci(n - 2);
}
return result;
}
}

运行时间与占用内存如下:

img
img

可是使用递归会有一个问题,会重复计算一些子问题。比如计算F(5)需要计算F(4)和F(3),计算F(4)需要计算F(3)和F(2),可以看到F(3)被重复计算了。造成了资源浪费。

所以我们换个思路。

动态规划

递归是将一个问题划分成多个子问题进行求解。动态规划相当于是个相反的过程,将子问题的解存储起来,用来解决大问题,比如已知F(0)、F(1),进行求F(2),再进一步求F(3),以此类推,直至求到F(n)。这样子就不会有重复求解子问题的烦恼产生。
实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int Fibonacci(int n) {
if (n <= 1){
return n;
}

int[] fib = new int[n+1];
fib[0] = 0;
fib[1] = 1;
for(int i = 2;i < n + 1; i++){
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
}

运行时间与占用内存如下:

img
img

这么做比递归好很多,但是考虑到第i项只与第i-1和第i-2项有关,因此只需要存储前两项的值就能求解第i项,从而将空间复杂度由O(N)降低为O(1)。所以我们可以进一步优化。

动态规划的进一步优化

使用两个值存储i-1和i-2,避免使用数组,浪费更多的空间。实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int Fibonacci(int n) {
if (n <= 1){
return n;
}
int preOne = 1; //存储i-1
int preTwo = 0; //存储i-2
int result = 0;
for(int i = 2;i < n + 1; i++){
result = preOne + preTwo;
preTwo = preOne;
preOne = result;
}
return result;
}
}

运行时间与占用内存如下:

img
img


接下来我们来看看剑指Offer中其他关于斐波那契数列的运用的题目:

题目一:跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

简单分析一下,就可以知道还是上面斐波那契数列的变化,青蛙跳1级台阶有1种跳法,2级台阶有2种跳法,3级台阶时可以从1级台阶跳上来也可以从2级台阶跳上来,即等于1级台阶的跳法加2级台阶的跳法因此n级台阶共有n-2级台阶跳法数+n-1级台阶跳法数。

实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int JumpFloor(int target) {
if(target <= 2)
return target;

int preOne = 2;
int preTwo = 1;
int result = 0;
for(int i = 3;i < target+1 ;i++){
result = preOne + preTwo;
preTwo = preOne;
preOne = result;
}
return result;
}
}
题目二:变态跳台阶

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

上一题的升级版,跳n级台阶时可以允许跳1~n任意阶级的台阶。

先来分析一下

  • 跳n级台阶,那么第一步有n种跳法:跳1级、跳2级、到跳n级
  • 跳1级,剩下n-1级,则剩下跳法是F(n-1);
  • 跳2级,剩下n-2级,则剩下跳法是F(n-2);
  • 所以F(n)=F(n-1)+F(n-2)+…+F(1)+1,最后的+1是因为直接跳n级台阶只有一种方法;
  • 因为F(n-1)=F(n-2)+F(n-3)+…+F(1)+1;
  • 以此类推,得F(n)=2*F(n-1)。

分析后变得比上面一提还要简单。实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int JumpFloorII(int target) {
if(target <= 2){
return target;
}

int preNum = 2;
int result = 0;
for(int i = 3;i < target + 1;i++){
result = 2 * preNum;
preNum = result;
}
return result;
}
}
题目三:矩阵覆盖

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形,总共有多少种方法?

再来分析一下

  • 首先从n=1开始,小矩阵只能竖着放,只有一种方法;
  • n=2时,大矩阵为2 * 2,小矩阵既可以竖着放也可以横着放,有两种方法;
  • 当n越来越大时,如果第一步选择竖着放,如下图:
    第一步:竖着放
    第一步:竖着放
    那么大矩阵的规模缩小成2 * (n-1);
  • 如果第一步选择竖着放,那么第二排也只能横着放,如下图:
    第一步:横着放
    第一步:横着放
    那么大矩阵的规模缩小成2 * (n-2);
  • 因此,题目又转化成了与题目一一样的斐波那契数列了。
    实现如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int RectCover(int target) {
if(target <= 2)
return target;

int preOne = 2;
int preTwo = 1;
int result = 0;
for(int i = 3;i < target+1 ;i++){
result = preOne + preTwo;
preTwo = preOne;
preOne = result;
}
return result;
}
}

以上就是关于斐波那契数列的含义和使用方式,题目一二三都是剑指Offer中的真题,示例中关于运行时间和占用内存是根据牛客网的测试用例得来的。