剑指Offer_斐波那契数列
题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
思路：首先对于这个**数列，就是n1=1；n2=2；n3=n1+n2；就是一个简单的递推关系式；这种递推关系的题目其实就是动态规划。
程序：
这个常规基于数组的，用了O（n）的额外空间；考虑到这个当前的状态之和前两个状态有关，所以我们只用把前两个状态记录下来即可，空间复杂度O（1），改进版如下；
Copy：
public int Fibonacci(int n) {
if(n<1)return 0;
else if(n<3)
return 1;
int dp[]=new int [n];
dp[0]=1;
dp[1]=1;
for(int i=2;i<n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n-1];
}
public int Fibonacci(int n) {
if(n<1)
return 0;
int first=1;
int second=1;
int third=2;
if(n<=2)
return 1;
for(int i=2;i<n;i++){
third=first+second;
first=second;
second=third;
}
return third;
}