10.1 斐波那契数列

题目链接

Leetcode

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。答案需要取模 1e9+7（1000000007）。

解题思路

如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。

递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。

每一项取模后都小于 1000000007，两项相加不超过 2000000012，小于 int 的最大值 2147483647，因此用 int 不会溢出；不取模时 f(47) 就会超出 int 的范围。

public int fib(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000007;
    return fib[n];
}

考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

public int fib(int n) {
    if (n <= 1)
        return n;
    int pre2 = 0, pre1 = 1;
    int fib = 0;
    for (int i = 2; i <= n; i++) {
        fib = (pre2 + pre1) % 1000000007;
        pre2 = pre1;
        pre1 = fib;
    }
    return fib;
}