斐波那契数列(剑指Offer-10.1)

题面

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

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

复制展开

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

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

示例

示例 1：

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

复制展开

示例 2：

1输入：n = 5
2输出：5

复制展开

限制

10 <= n <= 100

复制展开

思路

简单Fibonacci递推。

代码

1class Solution {
2public:
3    int fib(int n) {
4        int a[105] = {0, 1, 1};
5        for(int i=3; i<=100; i++)
6            a[i] = (a[i-1] + a[i-2]) % 1000000007;
7        return a[n];
8    }
9};