VIRTUALS

the virtual labs for the virtuals

0%

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

Posted on Edited on In , , ,

摘要：
动态规划入门题。

题目

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

$F(0) = 0, F(1) = 1$

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

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

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

示例 1：

输入： n = 2
输出： 1

示例 2：

输入： n = 5
输出： 5

提示：

  • $ 0 <= n <= 100 $

动态规划

考虑数字越界问题，需要在每一步求解时都进行求余运算。
循环求余证明：
设正整数 $ x, y, p$，求余符号为$⊙$，则有
$ (x + y) ⊙ p = (x ⊙ p + y ⊙ p) ⊙ p $
那么，在本题中：

$ f(n) ⊙ p = [f(n−1) ⊙ p + f(n−2) ⊙ p] ⊙ p $;

求 $f(n - 2)$ 时，将其更新为 $f(n - 2)$ 模以 $1000000007$;

求 $f(n - 1)$ 时，将其更新为 $f(n - 1)$ 模以 $1000000007$;

那么，根据上式，在求 $f(n)$ 时，将其更新为 $f(n - 2) + f(n - 1)$ 模以
$1000000007$ 显然正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 执行用时: 0 ms
// 内存消耗: 5.9 MB
class Solution {
public:
    int64_t _mod = 1e9 + 7;
    int fib(int n) {
        int64_t dp[110];
        dp[0] = 0, dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
            dp[i] %= _mod;
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 执行用时: 0 ms
// 内存消耗: 35.2 MB
class Solution {
    int _mod = 1000000007;
    public int fib(int n) {
        int[] dp = new int[110];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
            dp[i] %= _mod;
        }
        return dp[n];
    }
}

原题链接： 剑指Offer 10- I. 斐波那契数列