斐波那契数列是一系列数字，其中每个数字是前两个数字的和：

0, 1, 1, 2, 3, 5, 8, 13, ...

这是数学和编程中最著名的数列之一——而且它经常出现！

促使我写这篇简短博客的原因是一个有趣的例子，即在LeetCode的Climbing Stairs问题中使用斐波那契算法。

🪜 爬楼梯的故事

想象一下有一个有n级台阶的楼梯。

• 你可以一次爬1步。
• 或者一次跳2步（如果可能的话）。

你可以用多少种不同的方式到达顶部？

步骤模式
对于前几步：

步骤1 → 1种方式

步骤2 → 2种方式

1 + 1
2

步骤3 → 3种方式

1 + 1 + 1
1 + 2
2 + 1

步骤 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))