剑指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$ 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

示例 1：

输入： n = 2
输出： 1

示例 2：

输入： n = 5
输出： 5

提示：

• $0<=n<=100$

---

动态规划

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

$f(n)\odot p=[f(n-1)\odot p+f(n-2)\odot p]\odot p$;

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

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

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

• C++
• Java

// 执行用时: 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];
    }
};

// 执行用时: 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. 斐波那契数列