《算法：以三种算法思想及两种优化策略解决Fibonacci数》

作者的个人gitee

作者的算法讲解主页▶️

每日一言：“可堪孤馆闭春寒，杜鹃声里斜阳暮。🌸🌸”

斐波那契数作为算法入门的一道经典题目，在算法界具有重要地位，是学习算法的经典范例。

其递推公式简单而深刻，为动态规划、递归优化等算法提供了基础。今天小编便带着大家以三种不同的算法思想，搭配两种优化策略来解决这道经典例题。

0.题目

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

题目链接：509. 斐波那契数 - 力扣（LeetCode）

🔴一.递归+记忆化搜索

a.普通递归

时间复杂度：O（2^n）

class Solution {
public:int fib(int n) {if(n == 0 || n == 1)return n;elsereturn fib(n-1)+fib(n-2);}
};

b.记忆化搜索（优化）

算法讲解:

• 什么是记忆化搜索

就是带备忘录的递归。

在递归的过程中，我们可以发现在重复调用函数的过程中会重复计算很多已经计算过的子问题，如果我们将这些问题的答案存到备忘录里，那么下次计算到相同的子问题就可以直接在备忘录里找到答案并返回，大大优化了计算效率。

（备忘录可以是：容器、数组、哈希表…）

如图，要算f（4），f（2）就计算了两遍。

• 算法思想

将出现过的子问题的答案存到一个“备忘录”里，之后在调用函数时如果发现该问题已经出现过，则可以在备忘录里找到该问题的答案，直接返回。

时间复杂度：O（n）

class Solution {
public:int memo[31];//备忘录int fib(int n) {memset(memo,-1,sizeof memo);//数组每个元素初始化为-1，以防和递归过程中子问题出现的答案相同导致判断错误return dfs(n);//返回第n个斐波那契数}int dfs(int n){//此子问题的答案已经被算过，就在备忘录里找到答案直接返回if(memo[n] != -1)return memo[n];//处理边界情况if(n == 0 || n == 1){memo[n] = n;return n;}//将新子问题的答案存到备忘录里memo[n] = dfs(n-1)+dfs(n-2);return memo[n];}
};

🔴二.前缀和

a.算法讲解

前缀和算法是一种通过预处理数组来快速求解区间和的高效算法。它的核心思想是：预先计算并存储数组从起始位置到每个位置的累积和（即前缀和），从而在后续查询任意区间和时，能够通过简单的减法操作快速得出结果，大大减少了计算时间。

b.代码示例

class Solution {
public:void pre_fix(int n, vector<long long>& fib, vector<long long>& dp) {fib[0] = 0;fib[1] = 1;dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; ++i) {fib[i] = fib[i - 1] + fib[i - 2];dp[i] = dp[i - 1] + fib[i];}}
};

🔴三.动态规划+滚动数组

a.算法讲解

核心思想

• 最优子结构：问题的最优解包含其子问题的最优解。
• 重叠子问题：在递归求解过程中，相同的子问题会被多次计算。
• 状态转移方程：通过定义状态和状态之间的关系，将问题分解为子问题，逐步求解。

实现方式

• 自底向上（Tabulation）：从最小的子问题开始，逐步构建解决方案，直到求解原问题。
• 自顶向下（Memoization）：通过递归求解，将已计算的子问题结果存储起来，避免重复计算。

优点

• 高效性：避免重复计算，时间复杂度通常优于暴力解法。
• 适用性：适用于具有重叠子问题和最优子结构的问题，如背包问题、斐波那契数列等。

缺点

• 空间复杂度：通常需要额外的空间存储中间结果。
• 适用范围有限：不适用于没有重叠子问题或最优子结构的问题。

应用场景

• 算法设计：背包问题、最长公共子序列、最短路径问题等。
• 优化问题：资源分配、生产调度等。

b.普通动规代码示例

int fibonacci(int n) {if (n <= 1) return n;vector<int> dp(n + 1, 0);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

c.滚动数组优化

滚动数组简介

滚动数组是一种优化动态规划空间复杂度的技巧，通过仅保留必要的状态信息，减少存储空间的使用。

核心思想

• 动态规划通常需要存储所有子问题的解，但某些情况下，当前状态仅依赖于有限的几个前驱状态。
• 滚动数组利用这一特性，仅保留必要的前驱状态，从而将空间复杂度从O(n)优化到O(1)或更小。

实现方式

• 一维滚动数组：在斐波那契数列中，仅需保留前两个状态，通过滚动更新数组值。
• 二维滚动数组：在二维动态规划问题中，通过滚动更新行或列，减少空间占用。

优点

• 空间优化：显著减少动态规划的空间复杂度，节省内存。
• 效率提升：减少不必要的存储和访问操作，提高算法效率。

代码示例

int fibonacci(int n) {if (n <= 1) return n;int a = 0, b = 1;for (int i = 2; i <= n; ++i) {int c = a + b;a = b;b = c;}return b;
}

---

如有错误，恳请指正。