【leetcode】23. 数学-斐波那契数列

题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
难易程度：easy
 
示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一

分析

本题是经典的递归算法示例：
结束条件：F(0) = 0, F(1) = 1
递归公式：F(N) = F(N - 1) + F(N - 2)

时间复杂度：O(N^2)
空间复杂度：O(N)

ps:时间复杂度太高了，leetcode超时了。

代码

class Solution {
public:
    int fib(int n) {
        if (n == 0 ||n == 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
};

方法二

分析

本题也是动态规划的经典示例。

1. 状态定义：设dp为一维数组，其中dp[i]的值代表斐波那契数列第i个数字。
2. 转移方程：dp[i + 1] = dp[i] + dp[i - 1]，即对应数列定义 f(n + 1) = f(n) + f(n - 1)；
3. 初始状态：dp[0] = 0, dp[1] = 1，即初始化前两个数字；
4. 返回值： dp[n]，即斐波那契数列的第n个数字.

时间复杂度：O(N)
空间复杂度：O(N)

代码

class Solution {
public:
    int fib(int n) {
        vector<int> dp;
        dp.push_back(0);
        dp.push_back(1);
        for (int i = 2; i <= n; i++) {
            dp.push_back((dp[i-1] + dp[i-2]) % 1000000007);
        }
        return dp[n];
    }
};

方法三

分析

经典的动态规划方法较递归方法时间复杂度有所优化，但空间复杂度并没有优化。从动态规划方法中转移方程我们只用到了dp[i + 1]，dp[i]，dp[i - 1]三个元素，因此，我们只需要三个变量fibn，fib1，fib2即可，从而将空间复杂度降低到O(1)。

时间复杂度：O(N)
空间复杂度：O(1)

代码

class Solution {
public:
    int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int fib1 = 0, fib2 = 1;
        for (int i = 2; i <= n; i++) {
            int fibn = (fib1 + fib2) % 1000000007;
            fib1 = fib2;
            fib2 = fibn;
        }
        return fib2;
    }
};