题解 | 斐波那契数列

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int Fibonacci(int n) {
        // write code here
        int f[n+1];
        memset(f, 0, sizeof(f));
        f[1] = 1, f[2] = 1;
        for(int i = 3; i <= n; ++i){
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }
};

斐波那契数列数列大家都非常熟悉了，大类一般分为两种做法。递归和动态规划。

递归又分为重复和不重复的递归。

动态规划也分为保存全部值和只保存前两个值两种方法。

递归整体效率更低而且可能爆栈，不重复的递归好一点因为没有重复计算已经得到的值。

动态规划就是算到了前两个值然后算当前的值，初始化0和1就好，然后直接循环。

只保存前两个值更省空间，代码看起来更长一点。

我给的代码是保存全部值的动态规划，时间复杂度是O(n)，空间复杂度也是O(n)。