斐波那契数列

一、需求

写一个函数，输入 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。

二、迭代法

2.1  思路分析

考虑特殊情况，一直迭代就行

2.2  代码实现

class Solution { public int fib(int n) { if(n == 0 || n == 1) return n; int f0 = 0; int f1 = 1;; while(--n != 0) { int tmp = f1; f1 = (f0 + f1) % 1000000007; f0 = tmp; } return f1; } }

2.3  复杂度分析

时间复杂度为O(n)；空间复杂度为O(1)；

三、动态规划法

3.1  思路分析

首先考虑n == 0或n == 1这两种情况；定义dp[ ]数组，初始化dp[0]，dp[1]，从2开始到n，每次都要对1000000007取余，最后返回dp[n]。

3.2  代码实现

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

3.3  复杂度分析

时间复杂度为O(n)；空间复杂度为O(n)；