斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34它的第一个和第二个数字都为1，从第三项开始它的每个数字都是其前两项数字之和。
1.递归解法
由斐波那契数列的定义我们不难写出它的递归解法，代码如下：
public int Fibonacci(int n) {
if(n == 1 || n ==2){
return 1;
}
return Fibonacci(n-1) + Fibonacci(n - 2);
}由于递归解法每次都会进行方法压栈，如果所求的项数过多，可能会发生栈溢出，所以我们考虑用一个数组来保存斐波那契数列：
2.动态规划解法
代码如下：
public int Fibonacci2(int n) {
int[] array = new int[n];
array[0] = 1;
array[1] = 1;
for (int i = 2; i < array.length; i++) {
array[i] = array[i - 2] + array[i - 1];
}
return array[n - 1];
}3.优化后的动态规划解法
在第二种方法中我们用到了数组，数组的长度为要所求项的项数，在实际求第n项斐波那契数列的时候，实际上我们只关心它的前两项之和，并不关心它的之前项，所以我们再对其进行空间优化，并且给出初始状态（第一项和第二项都为1）.
代码如下：
public int Fibonacci3(int n) {
int temp1 = 1;
int temp2 = 1;
if(n == 1 || n ==2){
return temp1;
}
for (int i = 2; i < n; i++) {
int temp3 = temp1 + temp2;
temp1 = temp2;
temp2 = temp3;
}
return temp2;
}
