斐波那契数列是一系列数字，其中每个数字是前两个数字的和：
0, 1, 1, 2, 3, 5, 8, 13, ...
这是数学和编程中最著名的数列之一——而且它经常出现！
促使我写这篇简短博客的原因是一个有趣的例子，即在LeetCode的Climbing Stairs问题中使用斐波那契算法。
🪜 爬楼梯的故事
想象一下有一个有n级台阶的楼梯。
- 你可以一次爬1步。
- 或者一次跳2步（如果可能的话）。
你可以用多少种不同的方式到达顶部？
步骤模式
对于前几步：
步骤1 → 1种方式
步骤2 → 2种方式
步骤3 → 3种方式
步骤 4 → 5 种方法
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
你看到一个模式形成了吗？
1, 2, 3, 5...
这是斐波那契数列向右移动了一位！
为什么斐波那契在这里出现
要到达第 n 步，你的最后一步可以是：
从 n-1 走 1 步（例如 9 -> 10）
从 n-2 走 2 步（例如 8 -> 10）
因此，到达第 n 步的方式数量为：
𝑤𝑎𝑦𝑠(𝑛) = 𝑤𝑎𝑦𝑠(𝑛−1) + 𝑤𝑎𝑦𝑠(𝑛−2)
示例：
第 10 步 = 到达第 9 步的方式 + 到达第 8 步的方式
我们知道这是因为你可以在到达第 9 步的所有方式上加一个 1，这样就能到达第 10 步，
或者你可以将每种到达第8步的方法加上 2，这样就能到达第10步。
因此，通过将第8步的方法与第9步的方法相加，你可以得到到达第10步的所有组合。
这正是斐波那契规则！
在Python中编码斐波那契数列
一旦我们看到了这个模式，我们就可以直接编码斐波那契数列。
以下是一个生成前 n 个斐波那契数的简单函数：
def fibonacci(n: int) -> list[int]:
if n <= 0:
return []
# 从前两个斐波那契数开始
result = [0, 1]
# 构建到n的数列
for i in range(2, n):
result.append(result[i - 1] + result[i - 2])
return result[:n]
# 示例：前13个斐波那契数
print(fibonacci(13))