剑指Offer中关于斐波那契数列的分析和运用
我们先来看一下什么是斐波那契数列，这个应该在大一高数时大家都学过。
斐波那契数列（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*）
——《百度百科》
具体函数表达参考下面这张图。
斐波那契数列表达式
那么我们该如何求解与斐波那契数列相关的问题呢？
先看一下题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
具体可以用以下几种方法求解：
使用递归
递归能将一个问题划分成多个子问题进行求解。求F(n)时会转化成求F(n-1)、F(n-2),以此类推，最后转化成几个F(0)、F(1)相加的结果。实现如下：
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
可是使用递归会有一个问题，会重复计算一些子问题。比如计算F(5)需要计算F(4)和F(3)，计算F(4)需要计算F(3)和F(2)，可以看到F(3)被重复计算了。造成了资源浪费。
所以我们换个思路。
动态规划
递归是将一个问题划分成多个子问题进行求解。动态规划相当于是个相反的过程，将子问题的解存储起来，用来解决大问题，比如已知F(0)、F(1)，进行求F(2)，再进一步求F(3)，以此类推，直至求到F(n)。这样子就不会有重复求解子问题的烦恼产生。
实现如下：
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
这么做比递归好很多，但是考虑到第i项只与第i-1和第i-2项有关，因此只需要存储前两项的值就能求解第i项，从而将空间复杂度由O(N)降低为O(1)。所以我们可以进一步优化。
动态规划的进一步优化
使用两个值存储i-1和i-2，避免使用数组，浪费更多的空间。实现如下：
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
接下来我们来看看剑指Offer中其他关于斐波那契数列的运用的题目：
题目一：跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
简单分析一下，就可以知道还是上面斐波那契数列的变化，青蛙跳1级台阶有1种跳法，2级台阶有2种跳法，3级台阶时可以从1级台阶跳上来也可以从2级台阶跳上来，即等于1级台阶的跳法加2级台阶的跳法因此n级台阶共有n-2级台阶跳法数+n-1级台阶跳法数。
实现如下：
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)。
分析后变得比上面一提还要简单。实现如下：
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)；
- 因此，题目又转化成了与题目一一样的斐波那契数列了。
实现如下：
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中的真题，示例中关于运行时间和占用内存是根据牛客网的测试用例得来的。
