爬楼梯进阶：矩阵快速幂从O(n)到O(log n)

发布时间：2026/10/23 8:22:43
爬楼梯进阶：矩阵快速幂从O(n)到O(log n)
1. 为什么爬楼梯这道题值得用快速幂重新做一遍如果你刷过 LeetCode 的 70 题“爬楼梯”大概率第一反应是动态规划。dp[i] dp[i-1] dp[i-2]一个循环搞定代码短、思路直白看起来没有任何问题。我一开始也是这么写的直到有一次在讨论区看到有人提起“这题能用矩阵快速幂做到 O(log n)”我才意识到自己对这道题的理解其实停留在最表层。爬楼梯的题干大家都熟每次可以爬 1 级或 2 级台阶问爬到第 n 级有多少种不同的方法。n 的范围在 LeetCode 原题里是 1 到 45这个规模下 DP 的 O(n) 和快速幂的 O(log n) 在耗时上几乎没有肉眼可见的差别跑出来都是 0ms 级别。但问题是如果 n 变成 10^18 呢或者更实际一点如果这题出现在面试里面试官追问一句“你能不能把时间复杂度再降一档”你该怎么办这篇文章就是把这件事讲透从斐波那契数列的矩阵形式出发讲清楚怎么把爬楼梯的递推关系改写成矩阵乘法再讲快速幂怎么把 O(n) 的循环压成 O(log n) 的二进制拆分运算。全程 C 实现关键步骤给注释顺便把取模、整数溢出这类实际写代码时一定会踩的坑也一起说了。适用的人已经会用 DP 解爬楼梯、但对“更优解”只有模糊概念的刷题党准备面试、担心被追问复杂度的求职者以及对矩阵运算在算法题里的应用感兴趣、想建立“线性递推都能用矩阵快速幂加速”这个思维模型的人。2. 从 DP 到矩阵乘法爬楼梯的递推关系藏着一个线性代数结构先回到最基础的递推式。设f(n)表示爬到第 n 级台阶的方法数那么f(n) f(n-1) f(n-2)边界条件是f(1) 1f(2) 2。这个式子的含义很直观到达第 n 级台阶要么从第 n-1 级跨 1 步上来要么从第 n-2 级跨 2 步上来两种情况互斥所以方法数是两者之和。2.1 递推式的“状态”视角把两个连续项打包成向量DP 的写法是维护一个一维数组从左往右填。但如果我们换一个视角把“当前状态”定义为一个二维向量v(n) [ f(n) ] [ f(n-1) ]那么从v(n-1)到v(n)的转移能不能用一个矩阵来表示观察一下f(n) 1 * f(n-1) 1 * f(n-2) f(n-1) 1 * f(n-1) 0 * f(n-2)把这两行写成矩阵形式[ f(n) ] [ 1 1 ] [ f(n-1) ] [ f(n-1) ] [ 1 0 ] * [ f(n-2) ]定义转移矩阵M [[1, 1], [1, 0]]那么v(n) M * v(n-1)再往前推v(n) M^(n-2) * v(2)其中v(2) [f(2), f(1)]^T [2, 1]^T。所以问题从“算一个递推数列的第 n 项”变成了“算一个 2x2 矩阵的 n-2 次幂再乘一个向量”。这就是快速幂可以介入的地方。2.2 为什么这个改写不是“炫技”而是复杂度本质的改变DP 一次循环只算一个f(i)每一步依赖前一步的结果是一个天然的串行过程O(n) 跑不掉。而矩阵乘法有一个关键性质矩阵乘法满足结合律。这意味着M^8可以拆成(M^4)^2M^4可以拆成(M^2)^2于是幂次可以二分地“跳”上去算M^n只需要 O(log n) 次矩阵乘法而不是 O(n) 次。生活化一点理解DP 是爬楼梯一步一级想上到第 100 级就得走 100 步快速幂是坐电梯电梯每按一次键楼层数翻一倍按 7 次就能到 128 层。这种复杂度量级的差异在 n 很小的时候体现不出来但 n 一旦来到 10^9 级别O(n) 的循环可能需要几秒甚至更久而 O(log n) 的矩阵快速幂只需要几十次运算毫秒级出结果。2.3 从爬楼梯到斐波那契一个模型的两种面孔爬楼梯的递推式f(n) f(n-1) f(n-2)本质上就是斐波那契数列只是初始条件不同。经典斐波那契是F(0) 0, F(1) 1而爬楼梯是f(1) 1, f(2) 2。所以矩阵快速幂这套方法练会了爬楼梯这道题等于顺手把 LeetCode 上所有斐波那契类的题目都打通了——比如“第 N 个泰波那契数”这类题只需要把转移矩阵从 2x2 扩展成 3x3思路完全一致。这也是我建议大家不要只背 DP 写法的原因同一套递推骨架换一个数学视角就能覆盖一大类题目这个“迁移能力”才是刷题真正要训练的东西。3. 矩阵快速幂的完整推导从二进制拆分到 2x2 矩阵的乘法实现快速幂这个名字刷题的人通常第一反应是“整数的快速幂”比如算3^10 mod 1000。思路是把指数拆成二进制10 1010于是3^10 3^8 * 3^2幂次通过不断自乘得到指数通过位运算右移遍历。矩阵快速幂没有任何新东西就是把底数从整数换成矩阵乘法从整数乘法换成矩阵乘法仅此而已。3.1 整数快速幂的二进制原理先把这个彻底搞懂假设要算a^13。13 的二进制是1101也就是13 8 4 1。于是a^13 a^(841) a^8 * a^4 * a^1快速幂的做法是用一个变量base存储a^(2^i)初始时i 0base a。每次把指数右移一位同时base base * base让 base 变成a^2, a^4, a^8……在移位的过程中如果当前最低位是 1就把 base 乘到结果变量result里。C 代码长这样long long fastPow(long long a, long long n) { long long result 1; while (n 0) { if (n 1) { result * a; } a * a; n 1; } return result; }这段代码的关键点if (n 1)判断当前二进制位是否为 1n 1把指数右移a * a让底数加速自乘。循环次数等于 n 的二进制位数即log2(n)级别。3.2 从整数到矩阵把乘法规则换成矩阵乘法把上述代码里的整数换成 2x2 矩阵就得到了矩阵快速幂。C 里面表示矩阵最朴素的方式是定义一个结构体或者直接用vectorvectorlong long。考虑到性能和代码可读性之间的平衡我推荐用结构体加定长数组的方式因为 2x2 矩阵的乘法规则是固定的没必要用动态数组增加复杂度。矩阵乘法是快速幂的核心运算两个 2x2 矩阵相乘的公式先明确一下C[0][0] A[0][0]*B[0][0] A[0][1]*B[1][0] C[0][1] A[0][0]*B[0][1] A[0][1]*B[1][1] C[1][0] A[1][0]*B[0][0] A[1][1]*B[1][0] C[1][1] A[1][0]*B[0][1] A[1][1]*B[1][1]为什么 2x2 矩阵乘法是“左边行乘右边列”这个规则线性代数里的定义结果矩阵C[i][j]等于 A 的第 i 行与 B 的第 j 列对应元素乘积之和。这个规则不是拍脑袋来的它是为了保持线性变换的复合性质——先做变换 B 再做变换 A等价于一个变换矩阵 A*B。这个性质正是矩阵快速幂能够加速递推计算的数学根基。在 C 里实现 2x2 矩阵乘法建议先封装一个函数using Matrix arrayarraylong long, 2, 2; Matrix multiply(const Matrix a, const Matrix b) { return {{ {a[0][0]*b[0][0] a[0][1]*b[1][0], a[0][0]*b[0][1] a[0][1]*b[1][1]}, {a[1][0]*b[0][0] a[1][1]*b[1][0], a[1][0]*b[0][1] a[1][1]*b[1][1]} }}; }用std::array而不是vector因为大小在编译期就固定了没有堆分配性能更好代码也更接近“数学定义”本身。3.3 矩阵快速幂的完整实现模板化的幂函数有了乘法函数快速幂函数水到渠成Matrix identity() { return {{ {1, 0}, {0, 1} }}; } Matrix fastPow(Matrix base, long long exp) { Matrix result identity(); // 单位矩阵等价于整数快速幂中的 1 while (exp 0) { if (exp 1) { result multiply(result, base); } base multiply(base, base); exp 1; } return result; }这里有一个很容易忽略的点为什么初始 result 是单位矩阵而不是全 0 矩阵因为单位矩阵在矩阵乘法里的角色等同于整数里的 1。任何矩阵乘以单位矩阵都保持自身不变这保证了在指数二进制位为 0 的那些幂次被跳过时结果不会受到干扰。如果你把 result 初始化成全 0那么无论 exp 是什么最终结果都是全零矩阵——这是一个非常隐蔽、但几乎每个自己写过矩阵快速幂的人都会踩一次的坑。3.4 从矩阵幂到最终答案别忘了边界项的调整现在有了M^(n-2)之后怎么得到f(n)回顾前面的推导v(n) M^(n-2) * v(2)其中v(2) [f(2), f(1)]^T [2, 1]^T。所以f(n) M^(n-2)[0][0] * 2 M^(n-2)[0][1] * 1用代码表示int climbStairs(int n) { if (n 2) return n; Matrix M {{ {1, 1}, {1, 0} }}; Matrix powM fastPow(M, n - 2); return powM[0][0] * 2 powM[0][1] * 1; }到这里爬楼梯的矩阵快速幂解法已经完整了。但实际跑 LeetCode 的时候你可能会发现返回类型是int而矩阵里的中间结果可能超过int范围这里又涉及一个取模和类型选择的问题下一节细说。4. 实际提交时的几个坑取模、数据类型和边界条件理论推导再漂亮落到代码里总有几道坎。矩阵快速幂解爬楼梯我实际写的时候踩过几个坑逐个说一下。4.1 原题 n 只有 45为什么还要考虑溢出和取模LeetCode 70 题的 n 最大是 45这个规模下f(45)大约是 18 亿还在int范围内有符号 32 位整数的上限约 21.47 亿。所以如果只是为了过这道题用int也不会溢出。但问题是这个解法不该被限制在 45 以内。LeetCode 的讨论区里经常有人把题目改造成“如果 n 很大怎么办”面试官也可能追问。更常见的场景是如果题目要求结果对 1e97 取模比如 LeetCode 上很多动态规划题目的标准操作。这时候矩阵快速幂的优势才真正体现出来n 再大也能在几十次乘法内算出模意义下的答案。所以我的建议是直接用long long存储中间结果并在乘法过程中适时取模。这样代码既能应对原题的规模也能无缝扩展到“大 n 取模”的变体题。4.2 C 负数取模的坑%在中间结果上怎么用才对C 里%运算对负数的行为是结果符号跟随被除数。也就是说-1 % 1000000007的结果是-1而不是数学意义上的1000000006。在矩阵快速幂里如果所有输入都是非负的乘法结果也是非负的取模不会出现负数问题。这也是为什么我建议不要用“先乘再减”之类的小聪明来优化——保持矩阵元素始终非负取模就永远是安全的。const long long MOD 1000000007LL; Matrix multiply(const Matrix a, const Matrix b) { return {{ {(a[0][0]*b[0][0] % MOD a[0][1]*b[1][0] % MOD) % MOD, (a[0][0]*b[0][1] % MOD a[0][1]*b[1][1] % MOD) % MOD}, {(a[1][0]*b[0][0] % MOD a[1][1]*b[1][0] % MOD) % MOD, (a[1][0]*b[0][1] % MOD a[1][1]*b[1][1] % MOD) % MOD} }}; }注意每一对乘积相加前都先取了模避免两个long long相乘后再相加溢出long long。这一步在竞赛里叫“边乘边模”是避免溢出的标准姿势。4.3 n 为 1 和 2 时别让矩阵参与计算n 2时直接返回 n这个提前 return 不只是性能优化更是逻辑正确性的要求。因为矩阵快速幂基于M^(n-2)当n1时n-2为-1指数变成负数快速幂的循环根本不会执行返回的单位矩阵再乘v(2)得到的结果完全不对。更稳妥的做法是单独处理小规模情况。LeetCode 的climbStairs函数里用if (n 2) return n;一挡后面的矩阵运算就只处理n 3的情况安全又清晰。4.4std::array初始化一个容易编译报错的细节std::array的初始化方式比较死板必须用双花括号。我第一次写矩阵结构体时写成了单层花括号编译直接报错。正确写法是using Matrix arrayarraylong long, 2, 2; Matrix M {{ {1, 1}, {1, 0} }};外层花括号对应整个array内层花括号对应内部的每一个arraylong long, 2。如果嫌这个语法烦也可以用函数返回的方式Matrix matrix {{ {1, 1}, {1, 0} }};或者定义一个 helper 函数返回初始矩阵让调用处更简洁。这个细节写一次就会记住但第一次写的人大概率要被报错折磨几分钟。5. 完整题解代码与本地调试建议把上面的内容整合成一份可以在 LeetCode 上直接提交的完整 C 代码#include array using namespace std; using Matrix arrayarraylong long, 2, 2; const long long MOD 1000000007LL; Matrix multiply(const Matrix a, const Matrix b) { return {{ {(a[0][0]*b[0][0] a[0][1]*b[1][0]) % MOD, (a[0][0]*b[0][1] a[0][1]*b[1][1]) % MOD}, {(a[1][0]*b[0][0] a[1][1]*b[1][0]) % MOD, (a[1][0]*b[0][1] a[1][1]*b[1][1]) % MOD} }}; } Matrix identity() { return {{ {1, 0}, {0, 1} }}; } Matrix fastPow(Matrix base, long long exp) { Matrix result identity(); while (exp 0) { if (exp 1) { result multiply(result, base); } base multiply(base, base); exp 1; } return result; } class Solution { public: int climbStairs(int n) { if (n 2) return n; Matrix M {{ {1, 1}, {1, 0} }}; Matrix powM fastPow(M, n - 2); return (powM[0][0] * 2 % MOD powM[0][1] % MOD) % MOD; } };有人说 LeetCode 原题不要求取模你在代码里加了MOD会不会返回错误结果不会。因为原题 n 最大 45结果远小于 MOD取模前后值完全一致。加了 MOD 之后代码能跑原题也能跑任何“结果取模”的变体属于向前兼容。本地调试的时候我建议你手动跑几个小用例验证正确性n1 - 1 n2 - 2 n3 - 3111, 12, 21 n4 - 5 n5 - 8对应 LeetCode 的示例输出。如果这几个用例过了基本逻辑就不会有问题。6. 从爬楼梯到竞赛常用技巧矩阵快速幂还能加速什么样的递推爬楼梯只是矩阵快速幂最基础的应用场景。刷题圈子里流传一句话“一切线性递推都可以用矩阵快速幂加速到 O(log n)。”这句话怎么理解关键在于识别“线性”两个字。6.1 什么样的递推式能套矩阵快速幂线性递推的判定标准设一个序列的第 n 项可以由前面若干项的线性组合表示即满足形如F(n) a1*F(n-1) a2*F(n-2) ... ak*F(n-k)并且系数 a1..ak 是常数不随 n 变化那么这个递推式就一定能写成 k 维向量的矩阵转移形式。比如斐波那契是二阶线性递推F(n) F(n-1) F(n-2)对应 2x2 转移矩阵泰波那契是三阶线性递推T(n) T(n-1) T(n-2) T(n-3)对应 3x3 转移矩阵。如果递推式里带了常数项比如F(n) F(n-1) F(n-2) c只要把状态向量从 k 维扩展成 k1 维把常数 c 作为一维恒为 1 的分量放进去矩阵规模加一仍然可以处理。如果系数本身还随 n 变化矩阵快速幂就不适用了因为转移矩阵不再固定无法用幂运算合并多个转移步骤。6.2 LeetCode 里适合用矩阵快速幂热身/练手的几类题斐波那契数509最基本的 2x2 矩阵和爬楼梯几乎一样适合验证模板代码的正确性。第 N 个泰波那契数1137T(n) T(n-1) T(n-2) T(n-3)需要 3x3 矩阵可以练状态向量扩展的手感。铺瓷砖 / 多米诺骨牌类问题很多变体本质上是转移矩阵不同的线性递推识别出递推式以后直接套模板。一些组合计数类问题比如“用 1x2 和 2x1 的多米诺骨牌铺满 2xn 的棋盘”递推式恰好也是F(n) F(n-1) F(n-2)只是看起来和爬楼梯完全不同但数学结构一模一样。如果你把爬楼梯的矩阵快速幂源码存成一个模板遇到线性递推的题目时改一下状态维度和转移矩阵就能快速出解。这个模板的复用价值比单独背一道题的解法要大得多。6.3 选这个解法还是选 DP一个实用的决策建议很多读者会问面试碰到爬楼梯到底该写 DP 还是写矩阵快速幂我的建议是先花 30 秒写 DP 保证正确性再花一两分钟提一嘴“如果 n 很大可以用矩阵快速幂优化到 O(log n)”。面试官真正想考察的是你能不能意识到 DP 的解有时间复杂度上的天花板以及你有没有能力换一个数学视角重新建模。直接上来写矩阵快速幂一方面代码量大、容易出错另一方面如果面试官只是想看你有没有掌握基础 DP反而显得用力过猛。但在面试的追问环节矩阵快速幂是一个非常加分的“第二解”。能把递推改写成矩阵乘法、能解释清楚结合律为什么让幂运算可行、能分析出 O(log n) 的时间复杂度——这三步走完面试官对你的评价会明显上一个台阶。7. 一组快速验证的对照数据从 n1 到 n10 的爬楼梯结果算法题做到最后最怕的不是不会写而是写了但不知道自己写对没有。矩阵快速幂里有矩阵乘法、二进制拆分这些环节出错的地方比纯 DP 多所以一套可靠的对照数据特别重要。以下是从 n1 到 n10 的爬楼梯方法数都是手算DP 双重验证过的n方法数11223345586137218349551089这个数列就是斐波那契数列去掉第一项之后的结果。如果快速幂版代码跑出来的前 10 项和这张表完全一致说明矩阵乘法和幂次部分基本没有逻辑错误。再给一个稍大的值n 30时爬楼梯方法数是 1346269。n 40时是 165580141。n 45时是 1836311903注意这个数已经逼近int上限2147483647了所以原题才把 n 的上限定为 45——如果 n 再大一点int就装不下了。这也是 LeetCode 设计题目时留的一个“安全边界”细想挺有意思。如果你把 n 改到 50 甚至 100用 DP 跑没问题但用矩阵快速幂跑速度更快因为运算次数是 log n 级别。n 100的爬楼梯方法数是573147844013817084101这个数字已经远超long long的上限约 9.22e18所以实际竞赛中遇到大 n 一定会要求取模。取模版代码在这种情况下才是真正发挥价值的时候。8. 总结一下我对爬楼梯快速幂这个组合的实操体会这道题我前后用 DP、矩阵快速幂各写了一遍耗时上在 LeetCode 原题规模下没有区别但理解深度差别很大。DP 解法让我记住了递推公式矩阵快速幂解法让我真正理解了“为什么这个递推可以用更快的算法”。几个实操层面的经验和建议在这里一并分享第一矩阵快速幂的代码模板一定要独立存储。不要每次临时推倒重写。把multiply、identity、fastPow这三个函数作为固定模板保存下来遇到线性递推题目时只改矩阵维度、矩阵内容和最终取值公式能节省大量时间。我自己的模板放在本地一个独立的matrix_pow_template.h文件里刷题时直接拖过来用。第二取模别偷懒。即使原题不要求取模也建议在中间步骤加MOD常量。原因一是防止未来题目改造成大 n 场景原因二是培养边乘边模的肌肉记忆——等你真的遇到需要取模的题目时再临时改代码容易漏改某个乘法产生隐蔽 bug。我见过不止一个人因为中间某一处乘积没有取模导致整个答案错误且难以排查。第三面试时先给 DP 解再给快速幂解这个顺序不要乱。上来就秀矩阵运算如果面试官本身不熟悉线性代数你解释起来费劲不说还可能让他觉得你在背模板。先给出最直观、最稳妥的 DP 解法留下一个“有没有更优解”的尾巴等面试官追问时再引出矩阵快速幂节奏更自然也更符合真实工作中“先求正确、再求优化”的工程思维。爬楼梯这道题本身不难但它是通往“矩阵快速幂”这个强大算法家族的一扇门。把这道题彻底吃透后续遇到任何二阶、三阶、甚至更高阶的线性递推你都会比别的刷题者多一个趁手的工具。这也算是我刷题过程中少数几道“一道题带出一类题”的代表作了。