查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

• 前2个数是 0 和 1 。
• 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

 

1，用递归实现，lintcode提示超过时间

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

 2,用函数本身相加求和

class Solution{public:    /**     * @param n: an integer     * @return an integer f(n)     */    int fibonacci(int n) {        // write your code here        int t1=0,t2=1;        int t3=0;        int cnt=0;        //cnt =n;            if(n == 0)                return 0;            else if(n == 1)                return 1;            else            {                for(cnt = 2;cnt