fib.md

面试题10- I. 斐波那契数列

原题

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

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

示例 2： 输入：n = 5 输出：5

提示： 0 <= n <= 100 注意：本题与主站 509 题相同：https://leetcode-cn.com/problems/fibonacci-number/

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof

解法：DP

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

思路分析：

• 初学时候肯定都把斐波那契数列用递归来做，但是递归中有很多重复计算。
• 解决重复计算的问题一种是利用记忆化搜索，将已经计算过的结果保存起来，下次需要使用直接拿出来。
• 另外一种方式就是利用动态规划，设定边界条件，通过转移方程进行递推。本题中状态转移方程都已经写出来了，边界条件也给出了，所以直接动态规划即可。
• 这个题还要注意取模，斐波那契数列可以看做很多数累加，对最后累加的最后结果取余，与在相加过程中不断取余用余数相加是一样的。这里如果不在过程中取余，会导致超出32位而出错。
• 时间复杂度为$O(n)$，空间复杂度为$O(n)$。

运行结果：

• 执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户