题目：
题解
1、递归法（提交超时）
解题思路：把 f(n) 问题的计算拆分成 f(n-1) 和 f(n-2) 两个子问题的计算，并递归，以 f(0) 和 f(1) 为终止条件。
- 递归法会造成大量的重复计算，比如就计算fib(6)为例来看下
- 我们看到上面相同颜色的都是重复计算，当n越大，重复的越多
时间复杂度分析：
- 时间复杂度O(2^n)：二叉树的高度是 n - 1，一个高度为k的二叉树最多可以由 2^k - 1个叶子节点，也就是递归过程函数调用的次数，所以时间复杂度为 O(2^n)。
- 空间复杂度 O(n)：就是树的高度。
代码：
1
2
3
4
5
6
7
8
9
10// 递归法1
class Solution2 {
public int fib(int n) {
if (n < 2) return n;
int a = fib(n-1);
int b = fib(n-2);
int c = (a + b) % 1000000007;
return c;
}
}
2、记忆化递归法：
解题思路：当n越大，重复的越多，所以我们可以使用一个map把计算过的值存起来，每次计算的时候先看map中有没有，如果有就表示计算过，直接从map中取，如果没有就先计算，计算完之后再把结果存到map中。
复杂度分析：
- 时间复杂度O(n)：每次都只加2，故为O(n+2)，即O(n)
- 空间复杂度 O(n)：就是树的高度。
优化代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// 递归法2，优化，加入一个map集合用来存储之前算个的
class Solution3 {
public int fib(int n) {
return fib(n,new HashMap());
}
int fib(int n,Map<Integer,Integer> map) {
if (n < 2) return n;
if (map.containsKey(n)) return map.get(n);
int a = fib(n-1,map);
map.put(n-1,a);
int b = fib(n-2,map);
map.put(n-2,b);
int c = (a + b) % 1000000007;
map.put(n,c);
return c;
}
}
3、动态规划法
解题思路：以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。
复杂度分析：
- 时间复杂度 O(N) ： 计算 f(n)f(n) 需循环 n 次，每轮循环内计算操作使用 O(1)。
- 空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 动态规划法
class Solution {
public int fib(int n) {
int a = 0;
int b = 1;
// 记录每次的a+b，避免重复计算
int sum;
while (n-- > 0) {
sum = (a+b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}