7. 斐波那契數(shù)列

題目描述

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）。

注：n<=39

解題思路：

斐波那契數(shù)列：0, 1, 1, 2, 3, 5, 8 ......;

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

利用遞推公式：f(n) = f(n - 1) + f(n - 2);(當(dāng)n >= 2時)

時間復(fù)雜度O(n), 空間復(fù)雜度O(1)

解答：

class Solution {
public:
    int Fibonacci(int n) {
        int i = 0;
        int a = 0, b = 1;
        while(i < n)
        {
            b = a + b;
            a = b - a;
            ++I;
        }
        return a;
    }
};

大家有興趣可以訪問我的個人博客，不定時更新一些內(nèi)容哦！

圖片來自必應(yīng)壁紙