509、斐波那契数
斐波那契数，通常用 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$
> 链接：https://leetcode-cn.com/problems/fibonacci-number
# 题解
## 1、记忆化递归
用一个数组存储中间值，对已经计算过的值不再递归调用，将树形递归简化为线性递归。
```java
class Solution {
public int fib(int N) {
if (N < 2) {
return N;
}
int[] nums = new int[N+1];
nums[0] = 0;
nums[1] = 1;
return fib(N,nums);
}
private int fib(int N,int[] nums) {
// 0 + 1 case
if (N <= 2) {
return nums[0]+nums[1];
}
// has computed
if (nums[N-1] != 0 && nums[N-2] != 0) {
nums[N] = nums[N-1]+nums[N-2];
return nums[N-1]+nums[N-2];
}
// 递归调用
nums[N] = fib(N-1,nums) + fib(N-2,nums);
return nums[N];
}
}
2、空间优化
由于下一个数字只与前两个数字相关，可以利用两个辅助变量，从自底向上求解。
class Solution {
public int fib(int N) {
if (N < 2) {
return N;
}
int num1 = 0,num2 = 1;
while((N--) >= 2) {
int t = num1 + num2;
num1 = num2;
num2 = t;
}
return num2;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
