.jpg)
667 字
3 分钟
爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解题思路
- 动态规划核心：
- 定义
dp[i]为到达第i阶楼梯的方法数 - 状态转移方程：
dp[i] = dp[i-1] + dp[i-2]- 最后一步爬1阶 → 方法数 =
dp[i-1] - 最后一步爬2阶 → 方法数 =
dp[i-2]
- 最后一步爬1阶 → 方法数 =
- 定义
- 滚动变量优化：
- 只需要前两个状态（
prev和curr） - 迭代更新：
next = prev + curr
- 只需要前两个状态（
- 斐波那契本质：
- 方法数形成斐波那契数列
dp=1, dp=1, dp=2, ...
- 初始化边界：
dp=1（0阶时不动算1种方法）dp=1（1阶只有1种方案）
关键洞察
- 决策分解原理：
- 最后一步只有两种可能：爬1阶或爬2阶
- 总方案数 = 前一级方案数 + 前两级方案数
- 斐波那契数列特性：
- 数列：1,1,2,3,5,8,…（从F₀=1开始）
- 第
n阶解 = Fib(n)
- 空间优化关键：
- 当前状态仅依赖前两个状态
- 无需存储完整
dp数组
- 矩阵幂优化：
- 数学性质可用矩阵幂加速计算
- 时间复杂度优化至 O(log n)
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 基础递归 | O(2ⁿ) | O(n) | 指数级，不可用 |
| 记忆化递归 | O(n) | O(n) | 需哈希表存储中间结果 |
| 动态规划 | O(n) | O(n) | 完整DP数组 |
| 滚动变量 | O(n) | O(1) | 最优常用解法 |
| 矩阵幂 | O(log n) | O(1) | 数学最优解 |
代码实现
DP 滚动数组（滚动变量）
/** * @param {number} n * @return {number} */var climbStairs = function (n) { if (n == 1 || n === 2) return n; let pre1 = 1, pre2 = 2; let result = null; for (let i = 3; i <= n; i++) { result = pre1 + pre2; pre1 = pre2; pre2 = result; } return result;};矩阵幂
/** * @param {number} n * @return {number} */const climbStairs = (n) => { // 矩阵乘法 const multiply = (a, b) => [ [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]] ];
// 矩阵快速幂 const matrixPower = (mat, power) => { let result = [[1, 0], [0, 1]]; // 单位矩阵 while (power) { if (power & 1) result = multiply(result, mat); mat = multiply(mat, mat); power >>= 1; } return result; };
const q = [[1, 1], [1, 0]]; return matrixPower(q, n)[0][0];};