题目描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2输出2解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶示例 2输入n 3输出3解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶解题思路方法一动态规划核心思路状态定义dp[i] 爬到第i阶的方法数。状态转移要到达第i阶可以从第i-1阶爬 1 阶上来第i-2阶爬 2 阶上来dp[i] dp[i-1] dp[i-2]初始化dp[0] 1地面1 种方法dp[1] 1爬 1 阶1 种方法具体过程示例n 5idp[i]011122334558结果8✅代码实现写法1数组 DPclass Solution { public: int climbStairs(int n) { if (n 1) return 1; vectorint dp(n 1, 0); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; } };写法2滚动变量空间优化class Solution { public: int climbStairs(int n) { if (n 1) return 1; int prev2 1; // dp[0] int prev1 1; // dp[1] for (int i 2; i n; i) { int curr prev1 prev2; prev2 prev1; prev1 curr; } return prev1; } };写法3通项公式斐波那契class Solution { public: int climbStairs(int n) { double sqrt5 sqrt(5); double fib pow((1 sqrt5) / 2, n 1) - pow((1 - sqrt5) / 2, n 1); return round(fib / sqrt5); } };注意浮点数精度问题n 很大时可能出错。复杂度分析方法时间复杂度空间复杂度数组 DPO(n)O(n)滚动变量O(n)O(1)通项公式O(log n)O(1)关键细节1. 为什么是斐波那契数列dp[i] dp[i-1] dp[i-2]正是斐波那契的递推公式。dp[1] 1dp[2] 2dp[3] 3dp[4] 5dp[5] 82. 为什么dp[0] 1地面可以看作爬 0 阶有 1 种方法什么都不做。3. 和「斐波那契数」的区别题目区别509. 斐波那契数F(0)0, F(1)170. 爬楼梯dp[0]1, dp[1]1本质一样只是初始值不同。4. 如果每次可以爬 1、2、3 阶呢dp[i] dp[i-1] dp[i-2] dp[i-3]类似「三步问题」。方法二递归 记忆化代码实现class Solution { public: int climbStairs(int n) { vectorint memo(n 1, -1); return dfs(n, memo); } private: int dfs(int n, vectorint memo) { if (n 1) return 1; if (memo[n] ! -1) return memo[n]; memo[n] dfs(n - 1, memo) dfs(n - 2, memo); return memo[n]; } };复杂度时间 O(n)空间 O(n)方法三矩阵快速幂O(log n)代码实现class Solution { public: int climbStairs(int n) { if (n 1) return 1; vectorvectorlong long M {{1, 1}, {1, 0}}; vectorvectorlong long result matrixPow(M, n); return result[0][0]; } private: vectorvectorlong long matrixPow(vectorvectorlong long M, int n) { vectorvectorlong long result {{1, 0}, {0, 1}}; vectorvectorlong long base M; while (n 0) { if (n 1) result multiply(result, base); base multiply(base, base); n 1; } return result; } vectorvectorlong long multiply(vectorvectorlong long A, vectorvectorlong long B) { vectorvectorlong long C(2, vectorlong long(2, 0)); for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int k 0; k 2; k) { C[i][j] A[i][k] * B[k][j]; } } } return C; } };复杂度时间 O(log n)空间 O(1)四种方法对比方法时间复杂度空间复杂度推荐度滚动变量 DPO(n)O(1)⭐⭐⭐⭐⭐数组 DPO(n)O(n)⭐⭐⭐⭐矩阵快速幂O(log n)O(1)⭐⭐⭐通项公式O(log n)O(1)⭐⭐总结要点说明核心思想dp[i] dp[i-1] dp[i-2]初始化dp[0] 1dp[1] 1时间复杂度O(n)空间复杂度O(1)滚动变量 
长河君 · 2026/10/16 3:07:33 · 阅读 1.2k 【动态规划-22】70.爬楼梯
题目描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2输出2解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶示例 2输入n 3输出3解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶解题思路方法一动态规划核心思路状态定义dp[i] 爬到第i阶的方法数。状态转移要到达第i阶可以从第i-1阶爬 1 阶上来第i-2阶爬 2 阶上来dp[i] dp[i-1] dp[i-2]初始化dp[0] 1地面1 种方法dp[1] 1爬 1 阶1 种方法具体过程示例n 5idp[i]011122334558结果8✅代码实现写法1数组 DPclass Solution { public: int climbStairs(int n) { if (n 1) return 1; vectorint dp(n 1, 0); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; } };写法2滚动变量空间优化class Solution { public: int climbStairs(int n) { if (n 1) return 1; int prev2 1; // dp[0] int prev1 1; // dp[1] for (int i 2; i n; i) { int curr prev1 prev2; prev2 prev1; prev1 curr; } return prev1; } };写法3通项公式斐波那契class Solution { public: int climbStairs(int n) { double sqrt5 sqrt(5); double fib pow((1 sqrt5) / 2, n 1) - pow((1 - sqrt5) / 2, n 1); return round(fib / sqrt5); } };注意浮点数精度问题n 很大时可能出错。复杂度分析方法时间复杂度空间复杂度数组 DPO(n)O(n)滚动变量O(n)O(1)通项公式O(log n)O(1)关键细节1. 为什么是斐波那契数列dp[i] dp[i-1] dp[i-2]正是斐波那契的递推公式。dp[1] 1dp[2] 2dp[3] 3dp[4] 5dp[5] 82. 为什么dp[0] 1地面可以看作爬 0 阶有 1 种方法什么都不做。3. 和「斐波那契数」的区别题目区别509. 斐波那契数F(0)0, F(1)170. 爬楼梯dp[0]1, dp[1]1本质一样只是初始值不同。4. 如果每次可以爬 1、2、3 阶呢dp[i] dp[i-1] dp[i-2] dp[i-3]类似「三步问题」。方法二递归 记忆化代码实现class Solution { public: int climbStairs(int n) { vectorint memo(n 1, -1); return dfs(n, memo); } private: int dfs(int n, vectorint memo) { if (n 1) return 1; if (memo[n] ! -1) return memo[n]; memo[n] dfs(n - 1, memo) dfs(n - 2, memo); return memo[n]; } };复杂度时间 O(n)空间 O(n)方法三矩阵快速幂O(log n)代码实现class Solution { public: int climbStairs(int n) { if (n 1) return 1; vectorvectorlong long M {{1, 1}, {1, 0}}; vectorvectorlong long result matrixPow(M, n); return result[0][0]; } private: vectorvectorlong long matrixPow(vectorvectorlong long M, int n) { vectorvectorlong long result {{1, 0}, {0, 1}}; vectorvectorlong long base M; while (n 0) { if (n 1) result multiply(result, base); base multiply(base, base); n 1; } return result; } vectorvectorlong long multiply(vectorvectorlong long A, vectorvectorlong long B) { vectorvectorlong long C(2, vectorlong long(2, 0)); for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int k 0; k 2; k) { C[i][j] A[i][k] * B[k][j]; } } } return C; } };复杂度时间 O(log n)空间 O(1)四种方法对比方法时间复杂度空间复杂度推荐度滚动变量 DPO(n)O(1)⭐⭐⭐⭐⭐数组 DPO(n)O(n)⭐⭐⭐⭐矩阵快速幂O(log n)O(1)⭐⭐⭐通项公式O(log n)O(1)⭐⭐总结要点说明核心思想dp[i] dp[i-1] dp[i-2]初始化dp[0] 1dp[1] 1时间复杂度O(n)空间复杂度O(1)滚动变量