斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

這個數(shù)列從第3項開始，每一項都等于前兩項之和。

如果設(shè)F(n）為該數(shù)列的第n項（n∈N*），那么這句話可以寫成如下形式：:F(n)=F(n-1)+F(n-2)

顯然這是一個線性遞推數(shù)列。

數(shù)列應(yīng)用
算法：一個人爬樓梯，可以一次爬一階或者兩階，問n層樓梯有多少種爬法（來自字節(jié)跳動）

如果只有一階樓梯，那么很簡單，只有1種方法；如果有兩階樓梯呢，要么一次一階，要么一次兩階，2種方法；如果是三階呢，要么一次一階，要么先兩階后一階，要么先一階后兩階，唉，等等，是不是發(fā)現(xiàn)了什么，如果有三階的話，那么最后一步怎么走是不是有兩種，就是要么走一階，要么走兩階，如果走一階，前面還有兩階，入股走兩階，前面還有一階，那么前面的兩階或者一階怎么走呢，如果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);
        }
    }

上述遞歸的時間復(fù)雜度是 O(2^n)，用迭代實現(xiàn)復(fù)雜度為O(n)。
附上代碼

int fib5(int n)          //迭代實現(xiàn)
{
    int i,a=1,b=1,c=1;
    if(n<1)
    {
        return -1;
    }
    for(i=2;i<n;i++)
    {
        c=a+b;     //輾轉(zhuǎn)相加法（類似于求最大公約數(shù)的輾轉(zhuǎn)相除法）
        a=b;
        b=c;
    }
    return c;
}