首先，说一下斐波那契数列的定义：
又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），也就是下一个数值是它前紧邻两个数值的和。
直接上代码：
//方法一：最简单直接的方法，但是时间复杂度O(2^n)，空间复杂度o(1)
public class Solution{
public int Fibonacci(int n){
if(n<=1){
return n;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
//方法二：优化递归，时间复杂度O(n),空间复杂度O（n）
public class Solution {
public int Fibonacci(int n) {
int a[] = new int[40];
a[0] = 0;
a[1] = 1;
for(int i =2;i <= n; i++){
a[i] = a[i-1]+a[i-2];
}
return a[n];
}
}
//方法三：优化存储，时间复杂度O（n）,空间复杂度O（1）
public class Solution {
public int Fibonacci(int n) {
if(n<2){
return n;
}
//时间复杂度：O(n)
//空间复杂度：O（1）
int sum =0;
int two = 0;
int one = 1;
for(int i=2;i<=n;i++){
sum = two + one;
two = one;
one = sum;
}
return sum;
}
}
//方法四：在方法三的基础上持续优化
public class Solution{
public int Fibonacci(int n){
if(n<2){
return n;
}
int sum =1;
int one =0;
for(int i=2;i<=n;i++){
sum =sum +one;
one = sum -one;
}
return sum;
}
}
原文：https://www.cnblogs.com/gslgb/p/14530577.html