爬楼梯问题答案

### 爬楼梯算法题解及实现方法 #### 问题描述 给定一个整数 `n`，表示需要爬的楼梯总数。每次可以选择爬 1 或者 2 个台阶，计算共有多少种不同的方式可以爬到楼顶。 --- #### 方法一：递归法 递归的核心思想在于将大问题分解成更小的子问题解决。对于本题来说，到达第 `i` 阶楼梯的方式可以通过以下两种情况得到： - 到达第 `i-1` 阶后再走一步； - 到达第 `i-2` 阶后再走两步。 因此，状态转移方程为： \[ f(i) = f(i-1) + f(i-2) \] 边界条件为： - 当 \( n=1 \)，只有一种方法。 - 当 \( n=2 \)，有两种方法。 以下是 C++ 的递归实现代码： ```cpp int climbStairs(int n) { if (n == 1) return 1; // 边界条件 if (n == 2) return 2; // 边界条件 return climbStairs(n - 1) + climbStairs(n - 2); // 状态转移方程 } ``` 虽然这种方法直观易懂，但由于存在大量重复计算，时间复杂度较高，达到指数级别 \( O(2^n) \)[^1]。 --- #### 方法二：动态规划 为了避免递归中的重复计算，可以采用自底向上的动态规划方法来优化性能。通过记录中间结果减少冗余运算。 定义数组 `dp[i]` 表示到达第 `i` 阶楼梯的不同方法数量，则状态转移方程仍为： \[ dp[i] = dp[i-1] + dp[i-2] \] 初始条件为： - \( dp[1] = 1 \) - \( dp[2] = 2 \) 最终返回 \( dp[n] \) 即可。 下面是对应的 C++ 实现代码： ```cpp int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; 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) \)，空间复杂度同样为 \( O(n) \)[^2]。 --- #### 方法三：滚动数组优化 进一步观察发现，在上述动态规划中仅需保存最近两个状态即可完成当前状态的更新操作。因此可通过引入两个变量代替整个数组存储历史数据，从而降低空间开销至常量级 \( O(1) \)。 改进后的 C++ 实现如下所示： ```cpp int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int prev1 = 1, prev2 = 2, current = 0; for (int i = 3; i <= n; ++i) { current = prev1 + prev2; // 更新当前位置的结果 prev1 = prev2; // 移动前一位指针 prev2 = current; // 移动后一位指针 } return prev2; } ``` 该版本不仅保持了 \( O(n) \) 时间效率，还显著减少了内存占用[^3]。 --- #### 方法四：矩阵快速幂加速求解斐波那契序列 由于题目本质上是一个变体形式的斐波那契数列问题 (\( F_n=F_{n−1}+F_{n−2}\)) ，所以也可以利用矩阵乘法规则配合分治策略高效地获取任意项值而无需遍历全部过程。具体原理涉及线性代数知识以及模运算法技巧，此处不再赘述其细节部分。 C++ 版本示意代码省略... --- ### 结论 综上所述，“爬楼梯”问题是典型的动态规划入门案例之一，推荐优先选用 **动态规划** 或经过优化的空间节省版方案作为实际应用首选；而对于更高阶需求场景下考虑运用高级技术手段比如矩阵快速幂等方式提升整体表现效果[^4][^5]。