我GitHub上的：剑指offer题解​​​​​​​

斐波那契数列

题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

 

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

思路：由于数组下标是从0开始的，但是我们是看第几个的，所以我们设第0项的值为0，第1项为1。

                                                             

解法一：递归

public static int Fibonacci(int n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } return Fibonacci(n-1)+Fibonacci(n-2); }

上述递归的解法有很严重的效率问题，通过求解第10项的调用过程图来分析：

　　从上图中不难发现：在这棵树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。

时间复杂度：O(2^n)

解法二：非递归（迭代）

      改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多，我们只要想办法避免重复计算就行了

      输入n，那么我们就计算到F(n-1)(即第n个)，n是不确定的，所以用到动态数组ArrayList。

public static int Fibonacci(int n) { List<Integer> arr = new ArrayList<Integer>(); arr.add(0); arr.add(1); if (n <= 0 || n == 1) { return arr.get(n); } for(int i = 2; i <= n; i++){ arr.add(arr.get(i-1)+ arr.get(i-2)); } return arr.get(n); }

时间复杂度：O(n)

空间复杂度：O(n)

 

解法三：非递归（迭代）

如果不用ArrayList

public static int Fibonacci(int n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } int currOne = 0; int currTwo = 1; int result = 0; for (int i = 2; i <= n; i++) { result = currOne + currTwo; currOne = currTwo; currTwo = result; } return result; }

时间复杂度：O(n)

空间复杂度：O(1)

测试函数：

public static void main(String[] args) { int n = 3; int result = Fibonacci(n); System.out.println(result); }

 

如果考虑到n越来越大，那就要用到long的数据类型。

斐波那契数列的应用：

1.跳台阶+变态跳台阶

2.覆盖矩形