斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
这个数列从第3项开始，每一项都等于前两项之和。
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)
显然这是一个线性递推数列。
数列应用
算法：一个人爬楼梯，可以一次爬一阶或者两阶，问n层楼梯有多少种爬法（来自字节跳动）
如果只有一阶楼梯，那么很简单，只有1种方法；如果有两阶楼梯呢，要么一次一阶，要么一次两阶，2种方法；如果是三阶呢，要么一次一阶，要么先两阶后一阶，要么先一阶后两阶，唉，等等，是不是发现了什么，如果有三阶的话，那么最后一步怎么走是不是有两种，就是要么走一阶，要么走两阶，如果走一阶，前面还有两阶，入股走两阶，前面还有一阶，那么前面的两阶或者一阶怎么走呢，如果3阶的方法是f(3)，那么f(3)=f(2)+f(1),这么看来是不是明白多了，有人会说，如果大于3阶，比如有10000阶呢？即使有10000阶，那最后一步也是走两阶或者一阶，那么f(10000)=f(9999)+f(9998)，解决就是f(n)=f(n-1)+f(n-2)。
附上代码
public static int StepOfNum(int n){
if (n<=0){
return -1;
}
if (n==1){
return 1;
}
if(n==2){
return 2;
}
else{
return StepOfNum(n-1)+StepOfNum(n-2);
}
}
上述递归的时间复杂度是 O(2^n)，用迭代实现复杂度为O(n)。
附上代码
int fib5(int n) //迭代实现
{
int i,a=1,b=1,c=1;
if(n<1)
{
return -1;
}
for(i=2;i<n;i++)
{
c=a+b; //辗转相加法（类似于求最大公约数的辗转相除法）
a=b;
b=c;
}
return c;
}
