hlwang's Blog

理想主义青年永远不会被现实招安

0%

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

发表于 分类于
本文字数： 819 阅读时长 ≈ 1 分钟

题目描述

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

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

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

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

示例

示例1

1
2
输入：n = 2
输出：1

示例2

1
2
输入：n = 5
输出：5

提示

  • 0 <= n <= 100

思路1：递归

递归

因为F(N) = F(N - 1) + F(N - 2)，所以F(N - 1) = F(N - 2) + F(N - 3）,可以直接采用递归完成，递归的终止条件为n为0或1

递归代码

1
2
3
4
5
6
7
8
9
// 递归
class Solution
{
public:
    int fib(int n)
    {
        return (n == 0 || n == 1) ? n : (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
};

但是递归存在重复计算的问题，如图：计算F(N) 需要计算 F(N - 1) ， F(N - 2)，而计算F(N-1)又 需要计算 F(N - 2)， F(N - 3)， F(N - 2)重复计算了。

image-20230120110430351

思路2：自底向上递推

要计算F(N),可以先计算F(0),F(1),,,F(N-1),在计算F(N)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int fib(int n) {
        int F0 = 0;
        int F1 = 1;
        int ans;
        if (n <= 1 )
        {
            return n;
        }
        for (int i = 2; i <= n; i++)
        {
            ans = (F0 + F1) % 1000000007;
            F0 = F1 % 1000000007 ;
            F1 = ans % 1000000007 ;
        }
        return ans ;
    }
};