难度: Easy
斐波那契数 （通常用 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
提示：
0 <= n <= 30运行时间: 36 ms
内存: 14.7 MB
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a
# def fib(self, n: int) -> int:
# memo = [0] * (n + 1)
# return self.helper(memo, n)
# def helper(self, memo, n):
# if n <= 1:
# return n
# if memo[n] != 0:
# return memo[n]
# memo[n] = self.helper(memo, n-1) + self.helper(memo, n-2)
# return memo[n]
该题解实现了斐波那契数列的计算，采用迭代方法而非递归。定义两个变量a和b，初始值分别为0和1，对应斐波那契数列的F(0)和F(1)。在每次迭代中，将b的值赋给a，而b的新值为a和b之前的和，这样连续迭代n次后，a的值即为F(n)。这种方法避免了递归调用的重复计算，提高了效率。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义Solution类
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1 # 初始化斐波那契数列的前两个数字
for _ in range(n): # 进行n次迭代
a, b = b, a + b # 更新a和b的值
return a # 返回F(n)的值
使用两个变量a和b而不是数组来存储斐波那契数的主要原因是空间效率。在迭代求解斐波那契数时，每次计算只需要前两个数的信息，因此存储整个数列是不必要的。使用两个变量可以将空间复杂度从O(n)降低到O(1)，这对于大规模计算尤其有利。
是的，这种操作有可能导致数值溢出。由于斐波那契数列的增长速度非常快（指数级），当n较大时，a和b的值可能会超过编程环境所能表示的整数最大范围，从而导致溢出。不同的编程语言和环境对整数的最大值有不同的限制，例如在32位环境中，整数溢出更容易发生。
该迭代方法在n=0的情况下可以直接返回正确答案。在代码中，如果n为0，循环将不会执行（因为range(0)为空），直接返回初始值a，即0，这正是斐波那契数列中F(0)的值。因此，这种情况下无需特殊处理。
尽管这种基于迭代的方法在理论上可以用于计算很大的n值，但在实际应用中可能因为数值溢出和计算时间过长而不适用。对于非常大的n值，如n=10000，可以考虑使用其他算法优化，例如使用矩阵快速幂方法或者利用黄金分割比的近似公式。矩阵快速幂方法可以将算法的时间复杂度降低到O(log n)，显著提高计算大数的效率。