算法 2.1.2 斐波那契数【leetcode 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

算法思维

• 递归、动态规划

解题要点

• 使用动态规划的思想减少重复计算和函数的重复调用

解题思路

---

一. 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(2ⁿ)
  • n 层递归调用，每层分支成两个新的递归
  • 可以看成一个二叉树，树的节点数即为函数的调用次数
  • 调用次数为 2ⁿ-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 变形与延伸

=== 待续 ===