【LeetCode】动态规划—斐波那契数列（附完整Python/C++代码）

动态规划—#509. 斐波那契数列

• 前言
• 题目描述
• 基本思路
  • 1. 斐波那契数列的定义
  • 2. 理解递推关系
  • 3. 递归方法（直观但效率低）
  • 4. 动态规划方法 (高效)
  • • 步骤：
  • 5. 进一步优化: 只用常量空间
  • • 步骤:
  • 小总结:
• 代码实现
• • Python3代码实现
  • Python 代码解释
  • C++代码实现
  • C++ 代码解释

前言

这道题目是经典的 斐波那契数列 问题。题目要求给定一个整数

，返回第

个斐波那契数。

斐波那契数列的定义是:

• 对于

递推关系： 和爬楼梯问题类似，我们可以通过递推公式

来计算第

个斐波那契数。

LeetCode是一个广受欢迎的在线编程平台，专注于算法和数据结构的练习。它提供了数千道编程题目，涵盖从简单到困难的各种难度，帮助程序员提升解决问题的能力，准备技术面试，并加深对计算机科学基础知识的理解。 通过逐步解析不同类型的题目，希望能够帮助读者更好地理解算法的应用，掌握解题技巧，并提高编程能力。每篇文章将围绕特定的主题或算法展开，提供详细的解题思路以及代码实现。

题目描述

在这里插入图片描述

基本思路

1. 斐波那契数列的定义

斐波那契数列是一个从 0 开始的数列，后面的每一项是前两项的和:

• 第 0 项是

• 第1项是 1:

• 从第 2 项开始，每一项的值都是前两项的和:

, 其中

。

2. 理解递推关系

假设我们想计算第

项的斐波那契数

，我们可以利用递推关系：

• 先知道

和

，

• 然后通过公式

计算出

。

举个例子:

3. 递归方法（直观但效率低）

初学者可能会想到使用递归，即不停地调用

和

来得到结果。这是最直观的想法，但它的效率不高，因为很多计算会被重复执行。比如计算

时，会重复计算

等。

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

4. 动态规划方法 (高效)

为了解决递归中重复计算的问题，我们可以用动态规划，即从底向上计算，先计算小的数值，逐步推导出大的数值。

我们可以用一个数组来存储已经计算过的斐波那契数，从

和

开始，一步步推导到

。

步骤：

1. 设

表示第 i 个斐波那契数。

1. 初始化前两项:

。

1. 从第 2 项开始，依次计算：

，直到

。

1. 返回

。

这种方法不会有重复计算，因此效率非常高。

5. 进一步优化: 只用常量空间

其实我们不需要一个数组来存储所有的斐波那契数。因为在计算第

项时，我们只需要前两项

1) 和

，所以我们可以只用两个变量来记录这两项，不断向前推导。

步骤:

1. 先设置两个变量: prev1

和 prev2

，分别对应

和

。

1. 从第 2 项开始，逐步计算当前的斐波那契数 current = prev1 + prev2，然后更新 prev1 和 prev2 。
2. 继续这个过程，直到算到第 n 项。

小总结:

• 斐波那契数列的每一项是前两项的和，定义明确，可以用递归或动态规划解决。
• 递归方法直观但效率低，会有很多重复计算。
• 动态规划方法通过从小到大计算并存储中间结果，避免了重复计算，大大提高了效率。
• 空间优化方法只需要常量的空间存储前两项的值，是动态规划的进一步优化。

这就是斐波那契数列问题的基本思路。

代码实现

Python3代码实现

class Solution:
    def fib(self, n: int) -> int:
        # 如果 n 是 0 或 1，直接返回 n
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        # 使用两个变量来存储前两个斐波那契数，prev2 是 F(n-2)，prev1 是 F(n-1)
        prev2, prev1 = 0, 1
        
        # 计算从 F(2) 到 F(n) 的值
        for i in range(2, n + 1):
            # 当前的斐波那契数是前两个数的和
            current = prev1 + prev2
            # 更新前两个数，继续计算下一个
            prev2 = prev1
            prev1 = current
        
        # 最后 prev1 中保存的是 F(n)
        return prev1

Python 代码解释

1. Base Case: 如果

或

, 直接返回

，因为

。

1. 动态规划：使用两个变量 prev2 和 prev1 来存储前两个斐波那契数，避免使用数组来节省空间。
2. 循环：从 2 到 n 逐步计算斐波那契数，当前的值等于前两个值的和，然后更新 prev2 和 prev1 。
3. 最终结果: prev1 最终会存储

。

C++代码实现

class Solution {
public:
    int fib(int n) {
        // 如果 n 是 0 或 1，直接返回 n
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // prev2 保存 F(n-2)，prev1 保存 F(n-1)
        int prev2 = 0, prev1 = 1, current = 0;
        
        // 从 F(2) 到 F(n) 逐步计算
        for (int i = 2; i <= n; ++i) {
            // 当前的斐波那契数是前两个数的和
            current = prev1 + prev2;
            // 更新前两个斐波那契数
            prev2 = prev1;
            prev1 = current;
        }
        
        // 返回第 n 个斐波那契数
        return current;
    }
};

C++ 代码解释

1. Base Case: 如果

或

, 直接返回

。

1. 动态规划: 使用 prev2 和 prev1 变量存储前两个斐波那契数，以节省空间，不使用数组。
2. 循环：从 2 到 n 逐步计算每个斐波那契数，当前值等于 prev1 + prev2，然后更新这两个变量。
3. 返回结果: 最终 current 存储了

，并返回该值。