剑指 Offer 10- I. 斐波那契数列

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解题思路

解法一：递归

递归是最直观的方法，但也是最低效的。它通过将问题划分为较小的子问题来计算 Fibonacci 数。时间复杂度为指数级别，因为它会重复计算相同的子问题。

时间复杂度：O(2^n)，指数级别
空间复杂度：O(n)，递归调用堆栈的深度

解法二：动态规划

动态规划是一种更有效的方法，通过迭代计算斐波那契数，避免了重复计算。我们使用一个数组来存储中间结果，从 0 和 1 开始，逐步计算到 n。

时间复杂度：O(n)，线性级别
空间复杂度：O(n)，存储所有中间结果的数组

代码及结果

方法一

int Solution::fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

 

方法二

int fib(int n) {
        int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = (p + q)%MOD;
        }
        return r;
    }