当前位置：首页 > news >正文

LeetCode 70爬楼梯：除了动态规划，C++程序员还能用这几种骚操作解题？

news 2026/7/1 7:34:16

LeetCode 70爬楼梯：C++程序员的五种高阶解法实战

当你第一次在LeetCode上遇到爬楼梯问题时，动态规划可能是最直接的解法。但作为一名追求极致的C++程序员，你是否想过这个问题背后隐藏着更多可能性？让我们跳出思维定式，探索五种截然不同的解法，从时间复杂度O(n)到O(log n)，甚至O(1)的极致优化。

1. 动态规划的经典实现与空间优化

动态规划确实是解决爬楼梯问题的标准答案，但即便是这个"标准答案"，也有多种实现方式和优化空间。我们先从最基础的版本开始：

int climbStairs(int n) { if (n <= 2) return n; vector<int> 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]; }

这个版本使用了O(n)的空间复杂度，但实际上我们只需要保存前两个状态：

int climbStairs(int n) { if (n <= 2) return n; int prev = 1, curr = 2; for (int i = 3; i <= n; ++i) { int next = prev + curr; prev = curr; curr = next; } return curr; }

提示：在面试中，展示从基础版本到优化版本的思考过程，往往比直接给出最优解更能体现你的问题解决能力。

2. 数学公式法：斐波那契的闭式表达式

爬楼梯问题实际上是斐波那契数列的一个变种。斐波那契数列有一个著名的闭式表达式——比奈公式：

F(n) = (φ^n - ψ^n) / √5 其中 φ = (1+√5)/2 ≈ 1.618，ψ = (1-√5)/2 ≈ -0.618

在C++中实现这个公式需要注意浮点数精度问题：

#include <cmath> int climbStairs(int n) { const double sqrt5 = sqrt(5); const double phi = (1 + sqrt5) / 2; return round(pow(phi, n + 1) / sqrt5); }

这种方法的时间复杂度是O(1)，但要注意：

当n较大时，浮点数运算可能引入精度误差
在实际编程竞赛中，通常会预先计算一定范围内的结果

3. 矩阵快速幂：算法竞赛中的高级技巧

对于追求极致性能的场景，矩阵快速幂可以将时间复杂度降到O(log n)。这个方法的理论基础是斐波那契数列的矩阵表示：

[ F(n) ] = [1 1]^(n-1) [F(1)] [ F(n-1) ] [1 0] [F(0)]

C++实现如下：

#include <vector> using namespace std; vector<vector<long long>> multiply(vector<vector<long long>>& a, vector<vector<long long>>& b) { vector<vector<long long>> res(2, vector<long long>(2)); res[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0]; res[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1]; res[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0]; res[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1]; return res; } vector<vector<long long>> matrixPow(vector<vector<long long>>& a, int n) { vector<vector<long long>> res = {{1,0},{0,1}}; // 单位矩阵 while (n > 0) { if (n & 1) res = multiply(res, a); a = multiply(a, a); n >>= 1; } return res; } int climbStairs(int n) { if (n <= 2) return n; vector<vector<long long>> mat = {{1,1},{1,0}}; auto res = matrixPow(mat, n-1); return res[0][0] + res[0][1]; }

4. 递归与记忆化：理解问题本质

虽然纯递归解法在时间复杂度上不占优势（O(2^n)），但通过记忆化可以将其优化到O(n)：

#include <unordered_map> unordered_map<int, int> memo; int climbStairs(int n) { if (n <= 2) return n; if (memo.find(n) != memo.end()) return memo[n]; memo[n] = climbStairs(n-1) + climbStairs(n-2); return memo[n]; }

这种方法虽然不如迭代版本的动态规划高效，但在某些需要自顶向下思考的问题中更为直观。