1. 项目概述从一道经典面试题看算法思维爬楼梯问题但凡学过一点数据结构与算法或者刷过LeetCode的朋友绝对不陌生。题目描述简单到令人发指假设你正在爬楼梯需要n阶才能到达楼顶每次你可以爬 1 个台阶或者 2 个台阶。问你有多少种不同的方法可以爬到楼顶给定n是一个正整数。就是这么一个看似“小学生都能看懂”的题目却成了无数C初学者乃至求职者的“试金石”。为什么因为它完美地串联了从暴力递归、记忆化搜索、动态规划到矩阵快速幂乃至通项公式的整个算法思维演进链条。它不像八皇后问题那样复杂也不像某些大型项目那样需要庞大的工程能力但它像一把精巧的钥匙能打开“高效解决问题”这扇门。今天我就以一名老C程序员的角度带大家彻底拆解这道题不止于ACAccept通过更要明白每一种解法背后的“为什么”以及在实际编码中你会遇到哪些坑如何选择最优解。无论你是正在啃《C Primer》的新手还是在为面试“八股文”做准备的同学相信这篇深度剖析都能让你有所收获。2. 问题本质与数学模型建立在撸起袖子写代码之前我们必须先搞清楚我们在解决一个什么问题。这比盲目敲键盘重要十倍。2.1 核心需求解析什么是“不同的方法”题目问的是“不同的方法”。关键在于顺序很重要。爬1阶再爬2阶和爬2阶再爬1阶是两种不同的方法。这实际上是在求对于总阶数n使用1和2这两个数字进行有序拆分有多少种不同的组合方式。举个例子n31111221 这三种都是不同的方法。所以这不是简单的整数划分问题整数划分不关心顺序而是一个带顺序的组合问题。2.2 状态定义与递推关系推导这是将实际问题转化为数学模型的关键一步。我们定义f(i)为爬到第i阶楼梯的不同方法数。思考最后一步如果最后一步爬了1阶那么在此之前我们一定已经爬到了第i-1阶。爬到i-1阶有f(i-1)种方法。如果最后一步爬了2阶那么在此之前我们一定已经爬到了第i-2阶。爬到i-2阶有f(i-2)种方法。由于最后一步要么是1阶要么是2阶且这两种情况互斥不可能同时发生所以爬到第i阶的总方法数就是这两种情况的方法数之和。于是我们得到了那个著名的递推关系状态转移方程f(i) f(i-1) f(i-2)同时我们需要边界条件Base Case来启动这个递推f(1) 1爬到第1阶只有一种方法爬1阶。f(2) 2爬到第2阶有两种方法11 或直接2。敏锐的你一定发现了这个递推式和边界条件与斐波那契数列Fibonacci Sequence如出一辙。实际上f(n)就是斐波那契数列的第n1项如果我们定义 Fib(0)0 Fib(1)1。但请注意面试时直接说“这就是斐波那契数列”可能显得思考深度不够你需要清晰地阐述出上述推导过程。注意这里有一个初学者极易混淆的点。很多人会错误地认为f(0) 1“在平地有一种方法”。从数学递推的完备性上讲定义f(0)1可以使f(2)f(1)f(0)112也满足方程这有时是方便的。但在本题最直观的语境下n是正整数我们通常从f(1)和f(2)开始。在代码实现时要明确你采用的边界条件并保持逻辑一致。3. 解法一暴力递归——最直观的思维陷阱拿到递推公式f(n) f(n-1) f(n-2)几乎所有人的第一反应就是递归。class Solution { public: int climbStairs(int n) { if (n 1) return 1; if (n 2) return 2; return climbStairs(n - 1) climbStairs(n - 2); } };代码简洁明了完全对应数学模型。但是如果你在LeetCode上提交这个代码当n稍大比如45就会得到**“超出时间限制”**的判决。为什么3.1 时间复杂度分析指数级爆炸的根源让我们画出n5时的递归树f(5) / \ f(4) f(3) / \ / \ f(3) f(2) f(2) f(1) / \ / \ f(2) f(1) f(1) f(0)? // 取决于边界定义 / \ f(1) f(0)?你会发现f(3)被计算了两次f(2)被计算了三次。随着n增大这种重复计算呈指数级增长。其时间复杂度是O(2^n)这是一个非常恐怖的复杂度。n45时计算量已经大到无法接受。3.2 实操心得与教训永远不要在生产代码或面试中提交纯暴力递归解法除非面试官明确要求分析其缺陷。它唯一的作用是帮助你理解问题本质。递归是思考工具不一定是实现工具。先写出递归关系然后立刻思考如何优化这是正确的算法思维流程。这是讲解重叠子问题Overlapping Subproblems这一动态规划核心特征的绝佳例子。面试时你可以从这里自然引出对动态规划必要性的论述。4. 解法二记忆化递归自顶向下的动态规划既然纯递归的问题在于重复计算那么最直接的想法就是“记住”已经算过的结果。这就是记忆化搜索Memoization它本质上是动态规划的一种自顶向下的实现方式。class Solution { public: int climbStairs(int n) { // 使用一个数组或哈希表来充当“备忘录” vectorint memo(n 1, -1); // 初始化为-1表示未计算 return helper(n, memo); } private: int helper(int n, vectorint memo) { // 边界条件 if (n 1) return 1; if (n 2) return 2; // 查备忘录如果已经计算过直接返回结果 if (memo[n] ! -1) { return memo[n]; } // 计算并存入备忘录 memo[n] helper(n - 1, memo) helper(n - 2, memo); return memo[n]; } };4.1 核心改进与性能分析通过memo数组我们确保了每个子问题f(i)只被计算一次。计算f(n)时需要计算f(1)到f(n)所有值每个值计算是常数时间操作只是查表和加法。因此时间复杂度优化到了O(n)。空间复杂度也是O(n)用于存储备忘录。4.2 注意事项与编码细节备忘录初始化memo的大小是n1以便于下标直接对应楼梯阶数。初始化值必须是一个不可能的结果如-1用于判断是否已计算。私有辅助函数将核心递归逻辑封装在私有函数helper中是一种良好的工程实践保持了公共接口的简洁。与纯递归的对比记忆化递归的调用树从一棵巨大的、充满重复的树变成了一棵被“剪枝”后的、每个节点只访问一次的树。这是空间换时间的典型策略。适用场景记忆化搜索在解决某些状态定义复杂、依赖关系不那么直观的动态规划问题时非常有用因为它更贴近人类“递归思考”的方式。但对于爬楼梯这种线性递推问题我们通常会用更简洁的写法。5. 解法三动态规划自底向上的迭代这是面试中最常见、最期待的解法。我们完全摆脱递归从小问题开始一步步递推出大问题。class Solution { public: int climbStairs(int n) { if (n 2) return n; // 处理边界 // dp[i] 表示爬到第i阶的方法数 vectorint dp(n 1); // 初始化边界条件 dp[1] 1; dp[2] 2; // 状态转移 for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };5.1 动态规划四要素在本问题中的体现定义状态dp[i]就是f(i)即爬到第i阶的方法数。这是最关键的一步。状态转移方程dp[i] dp[i-1] dp[i-2]。这是问题的核心逻辑。初始状态dp[1] 1,dp[2] 2。这是递推的起点。计算顺序自底向上从i3循环到in。这保证了在计算dp[i]时dp[i-1]和dp[i-2]都已经计算好了。5.2 空间复杂度优化滚动数组观察状态转移方程dp[i]只依赖于前两个状态dp[i-1]和dp[i-2]。我们没有必要保存整个dp数组只需要保存最近的两个状态即可。这被称为滚动数组思想是动态规划空间优化的常见技巧。class Solution { public: int climbStairs(int n) { if (n 2) return n; int prev2 1; // 对应 dp[i-2]初始为 dp[1] int prev1 2; // 对应 dp[i-1]初始为 dp[2] int current; for (int i 3; i n; i) { current prev1 prev2; // 计算 dp[i] // 滚动更新状态为下一次迭代做准备 prev2 prev1; prev1 current; } // 循环结束时prev1 就是 dp[n] return prev1; } };优化后空间复杂度从O(n)降到了O(1)时间复杂度依然是O(n)。这是面试官非常希望看到的写法它展示了你对状态压缩的理解。实操心得在面试中你可以先写出标准的dp数组版本然后主动提出“由于状态转移只依赖于前两个状态我们可以用三个变量进行滚动优化将空间复杂度降到常数级。” 这会给面试官留下很好的印象。6. 解法四矩阵快速幂——对数级复杂度的降维打击当面试官问“还有更优的解法吗”或者题目中n的范围巨大比如n 10^18时O(n)的解法也不够看了。这时就需要数学武器矩阵快速幂。我们重新审视递推式[ f(n) ] [1 1] * [f(n-1)] [ f(n-1) ] [1 0] [f(n-2)]更一般地我们可以写成[ f(n) ] [1 1] ^ (n-2) * [f(2)] [ f(n-1) ] [1 0] [f(1)]令矩阵M [ [1,1], [1,0] ]初始向量F2 [f(2), f(1)]^T [2, 1]^T。 那么[f(n), f(n-1)]^T M^(n-2) * F2。问题的关键变成了如何快速计算矩阵M的(n-2)次幂。这里就用到了快速幂算法其原理基于二进制拆分和矩阵乘法的结合律能将幂运算的时间复杂度从O(n)降到O(log n)。class Solution { public: int climbStairs(int n) { if (n 2) return n; vectorvectorlong long base {{1, 1}, {1, 0}}; // 基础矩阵M vectorvectorlong long result matrixPower(base, n - 2); // 计算 M^(n-2) // 根据公式 [f(n), f(n-1)]^T M^(n-2) * [2, 1]^T // result * [2, 1]^T 的结果矩阵的第一行第一列就是 f(n) return result[0][0] * 2 result[0][1] * 1; } private: // 矩阵乘法 vectorvectorlong long multiply(const vectorvectorlong long a, const vectorvectorlong long b) { int size a.size(); vectorvectorlong long c(size, vectorlong long(size, 0)); for (int i 0; i size; i) { for (int j 0; j size; j) { for (int k 0; k size; k) { c[i][j] a[i][k] * b[k][j]; } } } return c; } // 矩阵快速幂 vectorvectorlong long matrixPower(vectorvectorlong long base, int power) { int size base.size(); // 初始化单位矩阵 vectorvectorlong long result(size, vectorlong long(size, 0)); for (int i 0; i size; i) { result[i][i] 1; } while (power 0) { if (power 1) { // 当前二进制位为1 result multiply(result, base); } base multiply(base, base); // 基数自乘 power 1; // 幂次右移一位 } return result; } };6.1 为什么需要 long long因为n很大时f(n)的值可能超出int的范围斐波那契数列增长很快。使用long long是防止溢出的良好实践。在面试中主动提出数据范围问题也是一个加分项。6.2 适用场景与评价时间复杂度O(log n)这是处理超大n时的唯一选择。空间复杂度O(1)忽略矩阵的固定大小。缺点代码实现复杂容易出错。在普通笔试或面试中除非明确要求或n范围极大否则O(n)的滚动数组解法通常是更优的选择因为它更易于编写、理解和调试。价值掌握这种方法体现的是你深厚的数学功底和解决更广泛线性递推问题如求解斐波那契数列第n项的能力。7. 解法五通项公式Binet‘s Formula——数学的优雅斐波那契数列有一个通项公式比内公式Fib(n) (φ^n - ψ^n) / √5其中φ (1√5)/2 ≈ 1.618黄金比例ψ (1-√5)/2 ≈ -0.618。由于climbStairs(n) Fib(n1)我们可以直接代入计算。在理论上这可以达到O(1)的时间复杂度如果认为 pow 函数是 O(1) 的话。class Solution { public: int climbStairs(int n) { n n 1; // 因为 climbStairs(n) 对应 Fib(n1) double sqrt5 sqrt(5); double phi (1 sqrt5) / 2; double psi (1 - sqrt5) / 2; // 使用 round 避免浮点数精度误差 return (int)round((pow(phi, n) - pow(psi, n)) / sqrt5); } };7.1 致命的精度问题这是该方法最大的陷阱。pow(phi, n)在n较大时比如n50会产生巨大的浮点数导致精度丢失。round函数也无法完全保证在所有情况下都能得到正确的结果。因此在要求精确结果的算法题或工程中绝对不要使用通项公式解法。7.2 它的意义何在尽管不实用但了解通项公式的存在是很有意义的理论价值它揭示了斐波那契数列与黄金比例之间的深刻联系。分析工具可以用来快速估算f(n)的数量级因为abs(ψ^n)很快趋于0所以f(n) ≈ φ^n / √5其增长是指数级的。面试谈资当面试官问“还有别的方法吗”你可以提到通项公式但必须紧接着指出其精度问题并说明为什么在实际编程中不采用。这展示了你的知识广度和批判性思维。8. 常见问题与排查技巧实录在实际编码和面试中围绕爬楼梯问题会产生一系列典型问题。8.1 问题排查表问题现象可能原因解决方案小数值测试正确大数值输出错误或溢出1. 使用int类型导致溢出。2. 递归解法超时。1. 使用long long或unsigned long long。2. 改用动态规划或矩阵快速幂。递归解法超时存在大量重复计算时间复杂度为 O(2^n)。引入备忘录记忆化搜索或直接改用迭代动态规划。动态规划数组访问越界没有处理好n1或n2的边界情况直接访问dp[1]、dp[2]。在函数开头添加if (n 2) return n;进行特判。滚动数组版本结果错误状态更新顺序错误。例如先prev1 current再prev2 prev1会导致prev2获得的是新的prev1值。严格按照current prev1 prev2; prev2 prev1; prev1 current;的顺序更新。矩阵快速幂结果错误1. 矩阵乘法实现错误行列循环顺序。2. 快速幂中对结果矩阵的初始化不对应是单位矩阵。3. 最后结果向量乘法系数用错。1. 仔细检查三重循环(i, k, j)或(i, j, k)的顺序确保是行乘列。2. 结果矩阵初始化为单位矩阵。3. 对照公式result[0][0]*2 result[0][1]*1检查。8.2 独家避坑技巧先写特判动手写动态规划代码时养成习惯第一行先处理n 2的情况。这能避免很多边界错误。画状态转移表对于不确定的DP在纸上画出dp数组前几项的值n1,2,3,4,5手动模拟一下。这是调试和验证思路的最快方法。从记忆化搜索到DP如果直接想DP方程有困难先写出记忆化递归的代码然后观察这个递归过程很容易就能转化为等价的迭代DP。这是一个非常实用的技巧。复杂度主动分析在面试中每给出一种解法都主动说出其时间、空间复杂度并简要说明原因。这体现了你的专业素养。思考扩展面试官可能会问“如果每次可以爬1、2、3阶呢” 或者 “如果每次可以爬1、2阶但其中某一阶比如第5阶坏了不能踩呢” 前者只需修改转移方程为f(i)f(i-1)f(i-2)f(i-3)并调整边界后者则需要在DP过程中遇到坏掉的台阶将其方法数设为0。能够快速应对这些变种说明你真正理解了模型。爬楼梯问题就像C算法学习路上的一个“麻雀”虽小五脏俱全。从最暴力的尝试到引入缓存的优化再到标准动态规划及其空间优化最后到运用数学工具进行极致优化它完整地展示了一个算法问题被层层剖析、不断优化的全过程。理解这个过程远比死记硬背十道难题的答案更有价值。下次再遇到类似的递推问题不妨想想我的“楼梯”应该怎么“爬” 从爬楼梯问题剖析C++算法：递归、动态规划与矩阵快速幂
1. 项目概述从一道经典面试题看算法思维爬楼梯问题但凡学过一点数据结构与算法或者刷过LeetCode的朋友绝对不陌生。题目描述简单到令人发指假设你正在爬楼梯需要n阶才能到达楼顶每次你可以爬 1 个台阶或者 2 个台阶。问你有多少种不同的方法可以爬到楼顶给定n是一个正整数。就是这么一个看似“小学生都能看懂”的题目却成了无数C初学者乃至求职者的“试金石”。为什么因为它完美地串联了从暴力递归、记忆化搜索、动态规划到矩阵快速幂乃至通项公式的整个算法思维演进链条。它不像八皇后问题那样复杂也不像某些大型项目那样需要庞大的工程能力但它像一把精巧的钥匙能打开“高效解决问题”这扇门。今天我就以一名老C程序员的角度带大家彻底拆解这道题不止于ACAccept通过更要明白每一种解法背后的“为什么”以及在实际编码中你会遇到哪些坑如何选择最优解。无论你是正在啃《C Primer》的新手还是在为面试“八股文”做准备的同学相信这篇深度剖析都能让你有所收获。2. 问题本质与数学模型建立在撸起袖子写代码之前我们必须先搞清楚我们在解决一个什么问题。这比盲目敲键盘重要十倍。2.1 核心需求解析什么是“不同的方法”题目问的是“不同的方法”。关键在于顺序很重要。爬1阶再爬2阶和爬2阶再爬1阶是两种不同的方法。这实际上是在求对于总阶数n使用1和2这两个数字进行有序拆分有多少种不同的组合方式。举个例子n31111221 这三种都是不同的方法。所以这不是简单的整数划分问题整数划分不关心顺序而是一个带顺序的组合问题。2.2 状态定义与递推关系推导这是将实际问题转化为数学模型的关键一步。我们定义f(i)为爬到第i阶楼梯的不同方法数。思考最后一步如果最后一步爬了1阶那么在此之前我们一定已经爬到了第i-1阶。爬到i-1阶有f(i-1)种方法。如果最后一步爬了2阶那么在此之前我们一定已经爬到了第i-2阶。爬到i-2阶有f(i-2)种方法。由于最后一步要么是1阶要么是2阶且这两种情况互斥不可能同时发生所以爬到第i阶的总方法数就是这两种情况的方法数之和。于是我们得到了那个著名的递推关系状态转移方程f(i) f(i-1) f(i-2)同时我们需要边界条件Base Case来启动这个递推f(1) 1爬到第1阶只有一种方法爬1阶。f(2) 2爬到第2阶有两种方法11 或直接2。敏锐的你一定发现了这个递推式和边界条件与斐波那契数列Fibonacci Sequence如出一辙。实际上f(n)就是斐波那契数列的第n1项如果我们定义 Fib(0)0 Fib(1)1。但请注意面试时直接说“这就是斐波那契数列”可能显得思考深度不够你需要清晰地阐述出上述推导过程。注意这里有一个初学者极易混淆的点。很多人会错误地认为f(0) 1“在平地有一种方法”。从数学递推的完备性上讲定义f(0)1可以使f(2)f(1)f(0)112也满足方程这有时是方便的。但在本题最直观的语境下n是正整数我们通常从f(1)和f(2)开始。在代码实现时要明确你采用的边界条件并保持逻辑一致。3. 解法一暴力递归——最直观的思维陷阱拿到递推公式f(n) f(n-1) f(n-2)几乎所有人的第一反应就是递归。class Solution { public: int climbStairs(int n) { if (n 1) return 1; if (n 2) return 2; return climbStairs(n - 1) climbStairs(n - 2); } };代码简洁明了完全对应数学模型。但是如果你在LeetCode上提交这个代码当n稍大比如45就会得到**“超出时间限制”**的判决。为什么3.1 时间复杂度分析指数级爆炸的根源让我们画出n5时的递归树f(5) / \ f(4) f(3) / \ / \ f(3) f(2) f(2) f(1) / \ / \ f(2) f(1) f(1) f(0)? // 取决于边界定义 / \ f(1) f(0)?你会发现f(3)被计算了两次f(2)被计算了三次。随着n增大这种重复计算呈指数级增长。其时间复杂度是O(2^n)这是一个非常恐怖的复杂度。n45时计算量已经大到无法接受。3.2 实操心得与教训永远不要在生产代码或面试中提交纯暴力递归解法除非面试官明确要求分析其缺陷。它唯一的作用是帮助你理解问题本质。递归是思考工具不一定是实现工具。先写出递归关系然后立刻思考如何优化这是正确的算法思维流程。这是讲解重叠子问题Overlapping Subproblems这一动态规划核心特征的绝佳例子。面试时你可以从这里自然引出对动态规划必要性的论述。4. 解法二记忆化递归自顶向下的动态规划既然纯递归的问题在于重复计算那么最直接的想法就是“记住”已经算过的结果。这就是记忆化搜索Memoization它本质上是动态规划的一种自顶向下的实现方式。class Solution { public: int climbStairs(int n) { // 使用一个数组或哈希表来充当“备忘录” vectorint memo(n 1, -1); // 初始化为-1表示未计算 return helper(n, memo); } private: int helper(int n, vectorint memo) { // 边界条件 if (n 1) return 1; if (n 2) return 2; // 查备忘录如果已经计算过直接返回结果 if (memo[n] ! -1) { return memo[n]; } // 计算并存入备忘录 memo[n] helper(n - 1, memo) helper(n - 2, memo); return memo[n]; } };4.1 核心改进与性能分析通过memo数组我们确保了每个子问题f(i)只被计算一次。计算f(n)时需要计算f(1)到f(n)所有值每个值计算是常数时间操作只是查表和加法。因此时间复杂度优化到了O(n)。空间复杂度也是O(n)用于存储备忘录。4.2 注意事项与编码细节备忘录初始化memo的大小是n1以便于下标直接对应楼梯阶数。初始化值必须是一个不可能的结果如-1用于判断是否已计算。私有辅助函数将核心递归逻辑封装在私有函数helper中是一种良好的工程实践保持了公共接口的简洁。与纯递归的对比记忆化递归的调用树从一棵巨大的、充满重复的树变成了一棵被“剪枝”后的、每个节点只访问一次的树。这是空间换时间的典型策略。适用场景记忆化搜索在解决某些状态定义复杂、依赖关系不那么直观的动态规划问题时非常有用因为它更贴近人类“递归思考”的方式。但对于爬楼梯这种线性递推问题我们通常会用更简洁的写法。5. 解法三动态规划自底向上的迭代这是面试中最常见、最期待的解法。我们完全摆脱递归从小问题开始一步步递推出大问题。class Solution { public: int climbStairs(int n) { if (n 2) return n; // 处理边界 // dp[i] 表示爬到第i阶的方法数 vectorint dp(n 1); // 初始化边界条件 dp[1] 1; dp[2] 2; // 状态转移 for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };5.1 动态规划四要素在本问题中的体现定义状态dp[i]就是f(i)即爬到第i阶的方法数。这是最关键的一步。状态转移方程dp[i] dp[i-1] dp[i-2]。这是问题的核心逻辑。初始状态dp[1] 1,dp[2] 2。这是递推的起点。计算顺序自底向上从i3循环到in。这保证了在计算dp[i]时dp[i-1]和dp[i-2]都已经计算好了。5.2 空间复杂度优化滚动数组观察状态转移方程dp[i]只依赖于前两个状态dp[i-1]和dp[i-2]。我们没有必要保存整个dp数组只需要保存最近的两个状态即可。这被称为滚动数组思想是动态规划空间优化的常见技巧。class Solution { public: int climbStairs(int n) { if (n 2) return n; int prev2 1; // 对应 dp[i-2]初始为 dp[1] int prev1 2; // 对应 dp[i-1]初始为 dp[2] int current; for (int i 3; i n; i) { current prev1 prev2; // 计算 dp[i] // 滚动更新状态为下一次迭代做准备 prev2 prev1; prev1 current; } // 循环结束时prev1 就是 dp[n] return prev1; } };优化后空间复杂度从O(n)降到了O(1)时间复杂度依然是O(n)。这是面试官非常希望看到的写法它展示了你对状态压缩的理解。实操心得在面试中你可以先写出标准的dp数组版本然后主动提出“由于状态转移只依赖于前两个状态我们可以用三个变量进行滚动优化将空间复杂度降到常数级。” 这会给面试官留下很好的印象。6. 解法四矩阵快速幂——对数级复杂度的降维打击当面试官问“还有更优的解法吗”或者题目中n的范围巨大比如n 10^18时O(n)的解法也不够看了。这时就需要数学武器矩阵快速幂。我们重新审视递推式[ f(n) ] [1 1] * [f(n-1)] [ f(n-1) ] [1 0] [f(n-2)]更一般地我们可以写成[ f(n) ] [1 1] ^ (n-2) * [f(2)] [ f(n-1) ] [1 0] [f(1)]令矩阵M [ [1,1], [1,0] ]初始向量F2 [f(2), f(1)]^T [2, 1]^T。 那么[f(n), f(n-1)]^T M^(n-2) * F2。问题的关键变成了如何快速计算矩阵M的(n-2)次幂。这里就用到了快速幂算法其原理基于二进制拆分和矩阵乘法的结合律能将幂运算的时间复杂度从O(n)降到O(log n)。class Solution { public: int climbStairs(int n) { if (n 2) return n; vectorvectorlong long base {{1, 1}, {1, 0}}; // 基础矩阵M vectorvectorlong long result matrixPower(base, n - 2); // 计算 M^(n-2) // 根据公式 [f(n), f(n-1)]^T M^(n-2) * [2, 1]^T // result * [2, 1]^T 的结果矩阵的第一行第一列就是 f(n) return result[0][0] * 2 result[0][1] * 1; } private: // 矩阵乘法 vectorvectorlong long multiply(const vectorvectorlong long a, const vectorvectorlong long b) { int size a.size(); vectorvectorlong long c(size, vectorlong long(size, 0)); for (int i 0; i size; i) { for (int j 0; j size; j) { for (int k 0; k size; k) { c[i][j] a[i][k] * b[k][j]; } } } return c; } // 矩阵快速幂 vectorvectorlong long matrixPower(vectorvectorlong long base, int power) { int size base.size(); // 初始化单位矩阵 vectorvectorlong long result(size, vectorlong long(size, 0)); for (int i 0; i size; i) { result[i][i] 1; } while (power 0) { if (power 1) { // 当前二进制位为1 result multiply(result, base); } base multiply(base, base); // 基数自乘 power 1; // 幂次右移一位 } return result; } };6.1 为什么需要 long long因为n很大时f(n)的值可能超出int的范围斐波那契数列增长很快。使用long long是防止溢出的良好实践。在面试中主动提出数据范围问题也是一个加分项。6.2 适用场景与评价时间复杂度O(log n)这是处理超大n时的唯一选择。空间复杂度O(1)忽略矩阵的固定大小。缺点代码实现复杂容易出错。在普通笔试或面试中除非明确要求或n范围极大否则O(n)的滚动数组解法通常是更优的选择因为它更易于编写、理解和调试。价值掌握这种方法体现的是你深厚的数学功底和解决更广泛线性递推问题如求解斐波那契数列第n项的能力。7. 解法五通项公式Binet‘s Formula——数学的优雅斐波那契数列有一个通项公式比内公式Fib(n) (φ^n - ψ^n) / √5其中φ (1√5)/2 ≈ 1.618黄金比例ψ (1-√5)/2 ≈ -0.618。由于climbStairs(n) Fib(n1)我们可以直接代入计算。在理论上这可以达到O(1)的时间复杂度如果认为 pow 函数是 O(1) 的话。class Solution { public: int climbStairs(int n) { n n 1; // 因为 climbStairs(n) 对应 Fib(n1) double sqrt5 sqrt(5); double phi (1 sqrt5) / 2; double psi (1 - sqrt5) / 2; // 使用 round 避免浮点数精度误差 return (int)round((pow(phi, n) - pow(psi, n)) / sqrt5); } };7.1 致命的精度问题这是该方法最大的陷阱。pow(phi, n)在n较大时比如n50会产生巨大的浮点数导致精度丢失。round函数也无法完全保证在所有情况下都能得到正确的结果。因此在要求精确结果的算法题或工程中绝对不要使用通项公式解法。7.2 它的意义何在尽管不实用但了解通项公式的存在是很有意义的理论价值它揭示了斐波那契数列与黄金比例之间的深刻联系。分析工具可以用来快速估算f(n)的数量级因为abs(ψ^n)很快趋于0所以f(n) ≈ φ^n / √5其增长是指数级的。面试谈资当面试官问“还有别的方法吗”你可以提到通项公式但必须紧接着指出其精度问题并说明为什么在实际编程中不采用。这展示了你的知识广度和批判性思维。8. 常见问题与排查技巧实录在实际编码和面试中围绕爬楼梯问题会产生一系列典型问题。8.1 问题排查表问题现象可能原因解决方案小数值测试正确大数值输出错误或溢出1. 使用int类型导致溢出。2. 递归解法超时。1. 使用long long或unsigned long long。2. 改用动态规划或矩阵快速幂。递归解法超时存在大量重复计算时间复杂度为 O(2^n)。引入备忘录记忆化搜索或直接改用迭代动态规划。动态规划数组访问越界没有处理好n1或n2的边界情况直接访问dp[1]、dp[2]。在函数开头添加if (n 2) return n;进行特判。滚动数组版本结果错误状态更新顺序错误。例如先prev1 current再prev2 prev1会导致prev2获得的是新的prev1值。严格按照current prev1 prev2; prev2 prev1; prev1 current;的顺序更新。矩阵快速幂结果错误1. 矩阵乘法实现错误行列循环顺序。2. 快速幂中对结果矩阵的初始化不对应是单位矩阵。3. 最后结果向量乘法系数用错。1. 仔细检查三重循环(i, k, j)或(i, j, k)的顺序确保是行乘列。2. 结果矩阵初始化为单位矩阵。3. 对照公式result[0][0]*2 result[0][1]*1检查。8.2 独家避坑技巧先写特判动手写动态规划代码时养成习惯第一行先处理n 2的情况。这能避免很多边界错误。画状态转移表对于不确定的DP在纸上画出dp数组前几项的值n1,2,3,4,5手动模拟一下。这是调试和验证思路的最快方法。从记忆化搜索到DP如果直接想DP方程有困难先写出记忆化递归的代码然后观察这个递归过程很容易就能转化为等价的迭代DP。这是一个非常实用的技巧。复杂度主动分析在面试中每给出一种解法都主动说出其时间、空间复杂度并简要说明原因。这体现了你的专业素养。思考扩展面试官可能会问“如果每次可以爬1、2、3阶呢” 或者 “如果每次可以爬1、2阶但其中某一阶比如第5阶坏了不能踩呢” 前者只需修改转移方程为f(i)f(i-1)f(i-2)f(i-3)并调整边界后者则需要在DP过程中遇到坏掉的台阶将其方法数设为0。能够快速应对这些变种说明你真正理解了模型。爬楼梯问题就像C算法学习路上的一个“麻雀”虽小五脏俱全。从最暴力的尝试到引入缓存的优化再到标准动态规划及其空间优化最后到运用数学工具进行极致优化它完整地展示了一个算法问题被层层剖析、不断优化的全过程。理解这个过程远比死记硬背十道难题的答案更有价值。下次再遇到类似的递推问题不妨想想我的“楼梯”应该怎么“爬”