题目描述
斐波那契数，通常用 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
算法思维
- 递归、动态规划
解题要点
- 使用动态规划的思想减少重复计算和函数的重复调用
解题思路
一. Comprehend 理解题意
- 每个数字由其前面两个数字计算得到
- 因此得到目标结果的必要条件是已知此前两数
二. Choose 选择数据结构与算法
递归解法
- 数据结构：-
- 算法思维：递归
三. Code 编码实现基本解法
class Solution {
public int fib(int N) {
//1.递归结束条件
if (N <= 1) {
return N;
}
//2.主体逻辑
//3.递归公式：F(n) = F(n-1) + F(n-2)
return fib(N - 1) + fib(N - 2);
}
}
执行耗时：8 ms，击败了 29.92% 的Java用户
内存消耗：35.5 MB，击败了 5.16% 的Java用户
时间复杂度：O(2n)
• n 层递归调用，每层分支成两个新的递归
• 可以看成一个二叉树，树的节点数即为函数的调用次数
• 调用次数为 2n-1 次
空间复杂度：O(n)
• 递归运算的空间复杂度 = 递归深度
四. Consider 思考更优解
改变算法思维
- 使用动态规划的思维减少函数的重复调用
五. Code 编码实现最优解
优化解法：动态规划解法
class Solution {
//简化版动态规划，临时变量只存放最近两个
public int fib3(int N) {
int pre_2 = 0, pre_1 = 0, current = 1;
for (int i = 1; i <= N; i++) {
pre_2 = pre_1;
pre_1 = current;
current = pre_1 + pre_2;
}
return current;
}
}
执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：35.3 MB，击败了 16.74% 的Java用户
时间复杂度：O(n)
• n 次遍历
空间复杂度：O(1)
• 三个用于记录数值的局部变量
六. Change 变形与延伸
=== 待续 ===
