斐波那契数列

7. 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

注：n<=39

解题思路：

斐波那契数列：0, 1, 1, 2, 3, 5, 8 ……;

这个数列从第3项开始，每一项都等于前两项之和。

利用递推公式：f(n) = f(n - 1) + f(n - 2);(当n >= 2时)

时间复杂度O(n), 空间复杂度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;
    }
};