题解-斐波那契数列

4种做法

最简单:
递归算法

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1)
        {
            return n;
        }

        return Fibonacci(n - 1) + Fibonacci(n - 2);

    }
};

时间复杂度

优化：动态规划：
状态转移方程:

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1)
        {
            return n;
        }
        int* dp = new int[n+1];
        dp[0] = 0 ;
        dp[1] = 1 ;

        for(int i = 2 ; i <= n;i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];

    }
};

时间复杂度
空间复杂度

进一步优化，我们发现每次计算只用到
那么保存2个临时变量即可。

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1)
        {
            return n;
        }
        int i_2 = 0;
        int i_1 = 1;
        int now;
        for(int i = 2 ; i <= n; i++)
        {
            now = i_2 + i_1;
            i_2 = i_1;
            i_1 = now;
        }
        return now;
    }
};

再进一步，可以发现
所以只需要1个临时变量即可：

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1)
        {
            return n;
        }
        int i_1 = 0;
        int now = 1;
        for(int i = 2 ; i <= n; i++)
        {
            now = now + i_1;
            i_1 = now - i_1;
        }
        return now;
    }
};