题目
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
- 0 ≤ N ≤ 30
方法一：递归
使用递归计算给定整数的斐波那契数。
上图表示了 fib(5) 计算过程的递归树
算法：
- 检查整数 N，如果 N 小于等于 1，则返回 N。
- 否则，通过递归关系：Fn = Fn-1 + Fn-2 调用自身。
- 直到所有计算返回结果得到答案。
public class Solution {
public int fib(int N) {
if (N <= 1) {
return N;
}
return fib(N-1) + fib(N-2);
}
}
复杂度分析
- 时间复杂度：O(2^N)。这是计算斐波那契数最慢的方法。因为它需要指数的时间。
- 空间复杂度：O(N)，在堆栈中我们需要与 N 成正比的空间大小。该堆栈跟踪 fib(N) 的函数调用，随着堆栈的不断增长如果没有足够的内存则会导致 StackOverflowError
方法二：记忆化自底向上的方法
自底向上通过迭代计算斐波那契数的子问题并存储已计算的值，通过已计算的值进行计算。减少递归带来的重复计算。
算法：
如果 N 小于等于 1，则返回 N。迭代 N，将计算出的答案存储在数组中。使用数组前面的两个斐波那契数计算当前的斐波那契数。知道我们计算到 N，则返回它的斐波那契数。
class Solution {
public int fib(int N) {
if (N <= 1) {
return N;
}
return memoize(N);
}
public int memoize(int N) {
int[] cache = new int[N + 1];
cache[1] = 1;
for (int i = 2; i <= N; i++) {
cache[i] = cache[i-1] + cache[i-2];
}
return cache[N];
}
}
复杂度分析
- 时间复杂度：O(N)。
- 空间复杂度：O(N)。
方法三：自底向上进行迭代
算法：
- 若 N <= 1，则返回 N。
- 若 N == 2，则返回 fib(2-1) + fib(2-2) = 1。
- 使用迭代的方法，我们至少需要三个变量存储 fib(N), fib(N-1) 和 fib(N-2)。
- 预置初始值：
-
- current = 0。
-
- prev1 = 1，代表 fib(N-1)。
-
- prev2 = 1，代表 fib(N-2)
- 我们从 3 计算到 N；0，1，2对应的斐波那契数是预先计算。
- 设置 current = fib(N-1) + fib(N-2)，因为 current 代表的是当前计算的斐波那契数。
- 设置 prev2 = fib(N-1)。
- 设置 prev1 = current。
- 当我们到达 N+1，将退出循环并返回 current。
class Solution {
public int fib(int N) {
if (N <= 1) {
return N;
}
if (N == 2) {
return 1;
}
int current = 0;
int prev1 = 1;
int prev2 = 1;
for (int i = 3; i <= N; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
}
复杂度分析
- 时间复杂度：O(N)。
- 空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。
以上是我之前能想到的方法。另外官方题解还有矩阵求幂以及利用黄金分割比的公式法，有兴趣看题解