版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

思路：

题目较简单，需要注意的是 输入参数N是1~N，比较常用思路是递归

方法一：无脑循环法

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        int f1 = 0;
        int f2 = 1;
        int tmp = 0;
        for(int i = 0; i < n - 2; i++){
            tmp = f1 + f2;
            f1 = f2;
            f2 = tmp;
        }
        return f2;
    }
}

方法二：递归 比较遗憾的是递归耗时比无脑循环多

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