題目：

查找斐波納契數(shù)列中第 N 個數(shù)。
所謂的斐波納契數(shù)列是指：
前2個數(shù)是 0 和 1 。
第 i 個數(shù)是第 i-1 個數(shù)和第i-2 個數(shù)的和。

斐波納契數(shù)列的前10個數(shù)字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

樣例
給定1，返回0

給定2，返回1

給定10，返回34

分析

開始刷LintCode的第一道題，也是很基礎(chǔ)的一道題。
斐波那契數(shù)列經(jīng)常用來講解遞歸的例子。
所以可以用遞歸的方法很方便的解決

遞歸

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        if(n == 1)
        {
            return 0;
        }
        else if(n == 2)
        {
            return 1;
        }
        else
        {
            return fibonacci(n-1) + fibonacci(n-2); 
        }
    }
}

這是用遞歸的方法解決，很清晰，幾乎是照搬了斐波那契數(shù)列的遞推式
但是遞歸算法的時間復(fù)雜度太高，提交之后并不通過

捕獲.PNG

非遞歸方法

所以需要嘗試非遞歸方法解決這個問題

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        if(n == 1)
        {
            return 0;
        }
        else if(n == 2)
        {
            return 1;
        }
        else
        {
            int s1 = 0;
            int s2 = 1;
            int sum = 0;
            int i = 3;
            while(i <= n)
            {
                sum = s1 + s2;
                s1 = s2;
                s2 =sum;
                i++;
            }
            return sum;
        }
    }
}

小結(jié)

以上就是斐波那契數(shù)列問題。
** 故不積跬步，無以至千里；不積小流，無以成江海 **
希望能慢慢堅持下去，從簡單到復(fù)雜的算法！