BM62　斐波那契数列¶

入门通过率 37.12%python3核心代码模式样例通过牛客 AC数组递归动态规划快速幂记忆化搜索

牛客原题　源码

讲解章节：DP 入门

一句话

求数列的第 n 项，用两个滚动变量往前推。

解题思路¶

这题考什么¶

「朴素递归 -> 记忆化 -> 递推 -> 滚动变量」这条优化链的最短示例，整个动态规划专题都建立在它之上，见 DP 入门。

状态定义：f[i] = 斐波那契数列的第 i 项，f[1] = f[2] = 1。转移方程：

f[i] = f[i - 1] + f[i - 2]        (i > 2)

照方程直接递归会把 f[i-1] 与 f[i-2] 两棵子树里重叠的子问题反复重算，调用次数是 O(2^n)；自底向上递推让每个子问题只算一次，降到 O(n)。再往下看一步：转移只回看两格，整张表里随时有用的永远只有相邻两项，于是连数组都不必开——a 记 f[i-1]、b 记 f[i]，每轮令 (a, b) = (b, a + b)。

数据规模与复杂度¶

n <= 40，时限 2 秒（其他语言）。递推做 n-1 次加法，时间 O(n)、空间 O(1)，正好命中题面要求的两个上界。唯一会超时的写法是朴素递归：2^40 约 1e12 次调用，任何语言都跑不完。 f[40] = 102334155，远在机器字长内，Python 的大整数不构成额外开销。

坑在哪¶

编号从 1 起算（f[1] = f[2] = 1），不是从 f[0] = 0 起算的那一套。代码用 a = 0、b = 1 起手，相当于把 i 摆在 1 上，再推 n-1 次让 b 落到 f[n]；循环次数写成 n 就整体错开一位，输出 f[n+1]。
答案在 b 里而不是 a 里。两个变量只差一步，返回错一个就整体偏移一项。
不要为了「写得像 DP」而开长度 n+1 的数组：题面把空间 O(1) 写成了硬要求，滚动变量才是这题的考点本身。

参考实现¶

solutions/nowcoder/BM62/sol.py
from typing import List, Optional


class Solution:
    def Fibonacci(self, n: int) -> int:
        # 题面保证 n >= 1；n <= 0 时按 f[0] = 0 的编号返回 0，与下面的起手值自洽
        if n <= 0:
            return 0
        # 滚动变量取代整张 dp 表：省掉的是「下标」这一维，只留转移用得到的两项
        a, b = 0, 1                 # a = f[i-1], b = f[i]，此刻 i = 1
        for _ in range(n - 1):      # 推 n-1 次，b 从 f[1] 一路走到 f[n]
            # 元组赋值的右侧先用本轮旧值算完再整体赋回，等价于 t = b; b = a + b; a = t
            a, b = b, a + b
        return b                    # 答案落在 b 上，a 停在 f[n-1]

BM62 斐波那契数列¶