在牛客上刷每日一题时碰到一道名为“波斐契那数列”的题目第一眼看到这名字我就笑了——这摆明是“斐波那契”的魔改版但点开题面之后发现它还真不只是换了个名字前三项给定初值从第四项起每一项都是前三项之和。这是一道很典型的递推类变体题考察的东西却一点都不少递推建模、边界条件、数据范围判断、还有一道隐藏的复杂度优化题。如果你正在准备算法面试或者刚开始刷题想拿递推动手这道题非常适合作为一轮完整的练习。我把它连同这段时间做的刷题 tracker 一起记了下来这篇就当是复盘笔记了。这道题表面上是“斐波那契的亲戚”实际上踩的坑比想象中多。我用暴力递归、记忆化、滚动数组、矩阵快速幂四种方式各写了一遍逐个对比耗时和适用场景也顺手整理了一份每日一题的打卡记录模板。全文不整虚的直接上思路和代码。1. 题目拆解波斐契那数列到底在考什么1.1 一个名字引发的误区先别急着写代码得把题目定义捋清楚。标准斐波那契是 F(n) F(n-1) F(n-2)初值 F(1) 1、F(2) 1。而“波斐契那数列”这个题目里通常给的定义是a1 1a2 1a3 1从第 4 项开始a(n) a(n-1) a(n-2) a(n-3)也就是说这不是二项递推而是三项递推属于 Tribonacci 这类高阶斐波那契的范畴。好多人和我一样看到名字下意识套斐波那契的公式结果样例都过不了。凡是递推题第一件事就是确认“前几项是什么”和“递推公式里有几项”这两点定错后面全白写。这种题的价值在于它把一个你熟悉的模型稍微改了一个维度考察的是你“能不能识别出递推结构”而不是“背没背过某个公式”。面试里遇到这类变体题考察点往往不是公式本身而是你把问题形式化、再选对解法的能力。1.2 四种解法的复杂度博弈拿到递推题我习惯先问自己三个问题n 的范围有多大对结果有没有取模要求运行时间限制是多少这三个答案直接决定了用什么级别的解法。先列出这道题可能出现的几种数据范围和对应策略数据范围推荐解法时间复杂度空间复杂度n ≤ 30暴力递归O(3^n)O(n)n ≤ 1e6滚动数组 DPO(n)O(1)n ≤ 1e6记忆化搜索O(n)O(n)n ≤ 1e18矩阵快速幂O(log n)O(1)看到这个表你应该懂了为什么不能用“上来就递归”的思路。递归在模型推导阶段非常好用因为它直接翻译数学公式逻辑不可能错但一旦数据范围到了 1e6指数级复杂度直接超时。滚动数组是常规解法代码短、性能稳大多数场景够用但如果是 1e18 这种大范围连 O(n) 都跑不动这时候必须上矩阵快速幂。我刷这道题时第一版就是暴力递归样例秒过然后提交直接 TLE。这就是典型的“局部正确但不是最终正确”。1.3 为什么最终解法倾向递推而不是递归递归是“自顶向下”分解问题递推是“自底向上”合并结果。两者在思想上等价但工程表现差别很大。暴力递归里有大量重复子问题比如算 a(50) 会把 a(49)、a(48)、a(47) 反复算很多遍指数爆炸就是这么来的。递推的核心优势有两个一是天然避免重复计算每个子问题只算一次二是空间可控借助滚动数组甚至可以把空间压到 O(1)。这道题用递推还有一个额外好处——能非常自然地过渡到矩阵快速幂因为矩阵快速幂本身就是对线性递推关系的批量加速。从这个角度说题目选择“波斐契那数列”而不是“斐波那契数列”其实是在逼你重新走一遍算法设计流程建模、分析、选型、优化。这套流程比背公式值钱得多。2. 核心细节解析与实操要点2.1 边界条件看似简单最容易翻车三项递推的边界条件比二项递推多了一个“初始项”。如果题目里明确写了 a1 a2 a3 1那 n ≤ 3 时要直接返回 1。有的题面会把索引从 0 开始也就是 a0 1、a1 1、a2 1此时 n 代表“第 n 1 项”判断条件就变成 n 3 返回 1。这个区别非常隐蔽。我见过不少人在本地测试时用 [1, 1, 1, 3, 5, 9] 这个序列当样例程序输出也对但提交就是错最后发现是索引偏移了一位。我的习惯是在写代码之前先把前几项手动列出来a1 1 a2 1 a3 1 a4 a3 a2 a1 3 a5 a4 a3 a2 5 a6 a5 a4 a3 9然后写程序时第一件事就是用一个 assert 验证前 6 项assert f(1) 1 assert f(2) 1 assert f(3) 1 assert f(4) 3 assert f(5) 5 assert f(6) 9这道题的边界坑本质上是“数学定义”和“计算机索引”的翻译误差提前用断言把这些基准值钉死后面怎么改代码都不怕改坏。2.2 取模运算别等结果算完再取如果题目要求结果对 1e97 取模那就意味着中间计算也要控制住数据规模。三项递推的数值增长非常快a4 还是 3a10 就已经超过 100 了到了 a100 就是天文数字。Python 虽然自带大整数支持但如果允许的编程语言是 C 或 Javaint 或 long long 在 a50 左右就会溢出。取模的规范做法是“边算边取”每一步加法完成之后立刻对 MOD 取模MOD 10**9 7 a, b, c 1, 1, 1 for i in range(4, n 1): a, b, c b, c, (a b c) % MOD有人喜欢先把三项加起来再取模然后抱怨答案不对多半是没注意到中间结果已经溢出了。Python 这里不明显因为你 print 出来都是完整的数但效率会下降C 选手就是直接 WA。记住一个原则只要题面要求取模就默认所有数据可能很大每一步运算都要带上 % MOD。2.3 用 tracker 管理每日一题进度标题里提到“tracker”我每天刷完题会把关键信息记到一个表格里它比单纯在题库里“已 AC 打卡”更有价值。因为 tracker 记录的不只是结果还有思路上的坑。我的每日一题 tracker 长这样日期题目核心考点实际用时是否一遍过错误原因收获04/15波斐契那数列递推、矩阵快速幂42 分钟否递归超时、索引错位数据范围要先看再定算法04/16..................这个表有几个栏位是后来补的核心考点、错误原因、收获。如果你只记录“做没做过”过两周再回头看等于没记录只有把考点和错误原因写清楚才能形成真正的复习素材。我会建议每天花三分钟填这一行刷题效率提升反而很明显因为定期回看这些记录能快速定位自己反复犯的错误类别而不是陷入无脑开新题的状态。3. 实操过程与核心环节实现3.1 第一步暴力递归打开思路拿到题先别管性能用最直接的方式把数学公式翻译成代码这一步的目的是保证思路不出错。Python 写起来就是def f(n): if n 1 or n 2 or n 3: return 1 return f(n - 1) f(n - 2) f(n - 3)这段代码样例绝对能过因为 a4 f(3) f(2) f(1) 3输出没问题。但如果你拿去跑 n 40明显能感觉到卡顿跑到 n 100 基本就等不完了。原因在于这个递归树每层分叉三次总数是 3^n 量级。它不是递推是灾难。所以暴力递归只能作为“逻辑验证工具”不能作为最终提交方案。很多时候先写一个正确但慢的版本再用它给后续优化后的版本做对拍是很实用的工程习惯。3.2 第二步记忆化搜索救场递归慢在重复计算那就把算过的结果存下来。Python 里最简单的方式是 functools.lru_cachefrom functools import lru_cache MOD 10**9 7 lru_cache(maxsizeNone) def f(n): if n 1 or n 2 or n 3: return 1 return (f(n - 1) f(n - 2) f(n - 3)) % MOD加上缓存之后每个 n 只计算一次递归调用总次数降到 O(n)。这个版本在 n ≤ 1e6 的时候能跑但 Python 递归默认深度大概是一千左右所以 n 一大就会直接 RecursionError。这时候要么用 sys.setrecursionlimit 强行调大递归深度要么干脆放弃递归改用迭代。我的建议是如果 n 只是几千记忆化很舒服如果 n 到百万级还是老老实实写循环。递归栈溢出的风险在实际面试中很容易成为隐藏扣分点能用迭代就优先迭代。3.3 第三步滚动数组 DP 是常规王牌迭代写法有几种最普通的是开一个长度为 n 1 的数组把前几项填进去然后循环求和。这种写法空间复杂度 O(n)可问题是这个数列本身不需要回头访问太远的数据只需要最近三项所以完全可以用三个变量滚动更新def tribonacci(n): if n 1 or n 2 or n 3: return 1 a, b, c 1, 1, 1 for i in range(4, n 1): a, b, c b, c, (a b c) % MOD return c这行a, b, c b, c, (a b c) % MOD是关键。它利用 Python 的并行赋值同时完成滚动更新不会出现“a 被覆盖后影响后续计算”的问题。如果你写成下面这种顺序赋值就错了# 错误示范 a b b c c a b c因为第一行把 a 覆盖成 b 之后第三行算a b c时用的就不是原来的 a 了。这种 bug 非常隐蔽不跑大数据很难发现。滚动数组把空间压到 O(1)时间复杂度保持 O(n)这是处理 1e6 以内数据的标准姿势。3.4 第四步矩阵快速幂应对超大 n如果题目把 n 拉到 1e18连 O(n) 都过不了此时必须用矩阵快速幂把时间复杂度降到 O(log n)。三项递推矩阵形式很固定[a(n) ] [1 1 1] [a(n-1)] [a(n-1)] [1 0 0] * [a(n-2)] [a(n-2)] [0 1 0] [a(n-3)]令转移矩阵为 T初始向量为 [a3, a2, a1]^T [1, 1, 1]^T则要算第 n 项只需要把 T 的 n-3 次方乘到初始向量上。Python 实现如下MOD 10**9 7 def mat_mul(A, B): n len(A) m len(B[0]) p len(B) res [[0] * m for _ in range(n)] for i in range(n): for k in range(p): if A[i][k] 0: continue for j in range(m): res[i][j] (res[i][j] A[i][k] * B[k][j]) % MOD return res def mat_pow(mat, power): size len(mat) res [[1 if i j else 0 for j in range(size)] for i in range(size)] while power: if power 1: res mat_mul(res, mat) mat mat_mul(mat, mat) power 1 return res def tribonacci_fast(n): if n 1 or n 2 or n 3: return 1 T [[1, 1, 1], [1, 0, 0], [0, 1, 0]] Tn mat_pow(T, n - 3) # 初始向量 [a3, a2, a1]^T [1, 1, 1]^T return (Tn[0][0] Tn[0][1] Tn[0][2]) % MOD注意矩阵乘法里我加了if A[i][k] 0: continue这个剪枝在稀疏矩阵上效果不错虽然 3x3 矩阵不明显但养成习惯是好的。矩阵快速幂的核心是“幂次按二进制拆解”和整数快速幂同理只不过乘法换成了矩阵乘法。实测一下 n 取几个典型值n10 返回 81我算一下a10 81 吗序列是 1,1,1,3,5,9,17,31,57,105a10105。我写代码的时候会拿这个基准值去验证矩阵版本防止矩阵写错。3.5 实测代码对拍与结果验证我自己跑了一遍三种解法用 n50、n1000、n10^18 三个档位测试解法n50n1000n10^18暴力递归卡死无法运行无法运行记忆化搜索毫秒级可能栈溢出无法运行滚动数组毫秒级毫秒级无法运行矩阵快速幂微秒级微秒级微秒级实际提交时如果题目只给 n ≤ 1e6滚动数组是最舒服的方案代码短、易调试、不容易写错只有当数据范围明确到 1e18 或者有多次查询时矩阵快速幂才值得上。很多新手一看到斐波那契变体就上矩阵快速幂反而因为矩阵乘法细节写错白白丢分。算法选型要贴合数据范围不是越高级越好。4. 常见问题与排查技巧实录4.1 索引错位从 1 开始还是从 0 开始这个坑我前面提过但值得单独再讲一次因为它是提交错误里最高发的一种。波斐契那数列如果定义 a1、a2、a3 为初始项那 n 就是“第 n 项”如果题目用数组下标 0 开始则 a0、a1、a2 为初始项此时题目可能问的是“第 n 个数”而不是“数列的第 n 项”。两者的判断分支是从 1 开始if n 3: return 1从 0 开始if n 3: return 1我发现最有效的排查方式是看题目给的样例输入输出。比如样例如果输入 4 输出 3那说明输入的是项号从 1 开始如果输入 3 输出 3那说明是从 0 开始。这个细节定下来再写代码比写完再猜要稳得多。4.2 取模翻车现场取模出问题主要有两种形态一是取模时机太晚中间结果溢出二是取模做过头比如在矩阵快速幂里把矩阵元素取模后乘法结果又超了范围。正确做法是每次加法或乘法后都立刻取模。还有一个小坑如果题目说结果对某个数取模但中间步骤里减法的取模需要先补正数。本题只有加法不涉及减法取模但如果是更复杂的递推记住处理负数时要用(x % MOD MOD) % MOD而不是直接% MOD。4.3 递归栈溢出Python 里的递归默认深度限制是 1000 左右无论记忆化还是暴力递归只要 n 超过这个值都会报 RecursionError。虽然可以用sys.setrecursionlimit(1000000)强行扩大但递归深度过大还会带来函数调用开销性能依然不理想。我的经验是递归只适合用来梳理思路最终提交尽量写迭代版本。这道题的滚动数组总共不到十行比递归加缓存更省心。面试时如果用了递归面试官追问“递归深度多少、栈溢出怎么办”想好这套解释再动手。4.4 滚动数组更新顺序错误前面已经展示过顺序赋值的错误版本。这种 bug 的特点是小 n 测试正确n 稍微大一点就开始偏差因为后续项全部用了被污染的数据。排查方法是打印出前几项和手算序列对照发现第 4 项往后的数值不对马上就能定位到更新逻辑。更稳的写法是直接用三个变量并行赋值或者用一个长度为 3 的列表配合取模下标循环arr [1, 1, 1] for i in range(4, n 1): arr[i % 3] (arr[(i - 1) % 3] arr[(i - 2) % 3] arr[(i - 3) % 3]) % MOD return arr[n % 3]这种方式在只有三个槽位的循环里非常好用但是要注意第 n 项到底存在哪个下标容易绕晕。两个方法选自己顺手的关键是别混着写。4.5 矩阵快速幂的乘法顺序坑矩阵乘法不满足交换律。Tn T^(n-3)之后如果初始向量在乘法式子的右侧那应该用矩阵乘向量如果强行把向量放左侧维度都配不上。我在初学阶段经常写反后来固定下来一套模板矩阵幂的结果是mat_pow(T, k)返回的是一个方阵然后我用方阵的第一行去点乘初始向量。如果你的语言里有现成的矩阵库直接用也行但面试里一般要求手写所以还是把这个 3x3 矩阵的推导过程吃透。另外矩阵幂里单位矩阵的初始化不要写错——3x3 单位矩阵是三个 1 分布在左上到右下对角线不是全 1 矩阵。4.6 常见问题速查表问题现象可能原因解决方案小 n 正确大 n 超时递归分支爆炸或循环次数过多用滚动数组或矩阵快速幂提交后答案错误索引从 0 还是从 1 判断错误用样例输入反推项号起点输出全是 0 或负数整型溢出取模太晚所有步骤都加 % MOD递归报 RecursionError递归深度超限改用迭代循环滚动数组结果与手算不符顺序赋值造成数据覆盖改成并行赋值矩阵快速幂结果异常矩阵乘法顺序写反验算 T 的几次幂与手推结果本地对拍通过仍 WA没有处理大数取模边界情况检查所有加法与乘法是否都取模这张表我是从自己踩坑和看别人提问里整理出来的基本覆盖了这类递推题的常见失分点。刷题时如果卡住了按表格逐条排查多数情况能快速定位。5. 从波斐契那扩展到通用递推模板5.1 一题藏着一类题的解法这道题做完之后我做了一个小总结二项递推用斐波那契模板三项递推用 Tribonacci 模板K 项递推就构造 K 维矩阵。规律其实非常统一。比如四阶递推“前四项为 1从第五项起每项是前四项之和”转移矩阵就是一个 4x4 的矩阵[1 1 1 1] [1 0 0 0] [0 1 0 0] [0 0 1 0]也就是说只要递推公式是线性的、常系数的都可以用矩阵快速幂加速。面试中遇到这类题识别出“线性递推”四个字解题框架就自动出现了。我在 tracker 里给这道题打了一个标签“线性递推模板”之后遇到同类题直接把这段矩阵代码复制过去改维数省了不少时间。这也是刷题记录能带来的复利一道题的知识沉淀会反复在后续题目里兑现。5.2 经验之谈先看范围再定解法最后写代码整个波斐契那数列的练习做下来最大的收获不是什么数学知识而是做题顺序的调整。以前我拿到题会立刻打开编辑器写代码现在我会先花一分钟在草稿纸上列三个东西递推公式、初始边界、数据范围。数据范围直接决定算法复杂度这一点在几乎所有算法题里都适用。还有一点值得单独说不要因为矩阵快速幂更“高级”就忽略滚动数组。在真实开发或者面试场景中答案的正确性、可读性和维护成本同等重要。能用十行代码解决的事情不要刻意写成一百行炫技。把每种解法的适用边界吃透比单纯背模板有用得多。我在实际调试中还有一个习惯算是压箱底的技巧拿到任何递推题先把前 10 项手算出来写在代码注释里然后再写逻辑。这样不管后面怎么优化都有一个“标准答案”做对照能瞬间定位错误。波斐契那这道题我前 10 项是 1、1、1、3、5、9、17、31、57、105每次改完代码先跑一遍这 10 个数全对再提交基本不会翻车。这个习惯看起来笨但确确实实帮我避开了无数次改错改回来又改回去的循环。
