题目描述

难度：


简单


写一个函数，输入 n，求斐波那契（Fibonacci）数列的第 n 项（即 F(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

来源：力扣（LeetCode）

链接：

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof

思路（动态规划）

思路

此类题目如果用递归完成，则很可能超时（此处不演示）。常用的方法为动态规划或记忆化搜索。以下代码为动态规划的思路。

首先创立 n + 1 大小的数组，给定前两个元素的值，之后每一项都依据递推公式得出。

代码

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

执行结果

写在最后

本系列博客仅记录转码过程中刷题时的解法。若有错误，欢迎交流与批评指正。官方解法请见力扣（LeetCode）官网。