斐波那契数列

题目描述

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

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

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

1
2
输入:n = 2
输出:1

示例 2:

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

提示:
0 <= n <= 100

题目链接

Leetcode

题目解答

解法一

由递推公式,我们很容易写出求解数列第n项的递归形式,当n比较小的时侯可以直接得到结果,但是递归求解的时间复杂度是指数级别的,随着n的增大,计算所需耗费的时间也是呈指数增长,当n比较大的时侯,不推荐使用递归求解。

时间复杂度:$O(2^n)$ 空间复杂度:$O(1)$

1
2
3
4
5
6
class Solution {
public int fib(int n) {
if (n <= 1) return n;
return (fib(n - 1) + fib(n - 2)) % 1000000007;
}
}

超出时间限制,最后执行的输入:43

解法二

从斐波那契数列的定义出发,我们可以使用迭代法求解数列的第n项。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int fib(int n) {
if (n == 0) return 0;
if (n <= 2) return 1;
int a = 1, b = 1, c = 2;
for (int i = 2; i < n; i++) {
c = a + b;
c %= 1000000007;
a = b;
b = c;
}
return c;
}
}

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:35.1 MB, 在所有 Java 提交中击败了88.73%的用户

-------------本文结束 感谢您的阅读-------------

文章对您有帮助,可以打赏一杯咖啡,鼓励我继续创作!