LeetCode 70：爬楼梯｜递归到动态规划全路径解析_爬楼梯算法 动态规划

本篇博客将通过 LeetCode 第 70 题 “Climbing Stairs”为例，系统讲解从递归暴力解法到记忆化搜索、再到动态规划及空间优化的四种典型思路，适合算法初学者深入掌握递归与 DP 基础。

文章目录

• LeetCode 70 | 爬楼梯
• • 一、题目描述
  • 二、思路分析
  • 三、方法一：递归（不带记忆）
  • • 思路
    • C++代码
  • 四、方法二：递归 + 记忆化搜索（Top-Down DP）
  • • 思路
  • 五、方法三：动态规划（Bottom-Up）
  • • 思路
  • 六、方法四：动态规划 + 空间优化
  • • 思路
• 总结

LeetCode 70 | 爬楼梯

掌握这个题目，不仅能加深对递归与动态规划的理解，还为今后应对更复杂的算法题奠定坚实基础。

推荐初学者从这题入手，逐步建立起算法思维框架！

一、题目描述

你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
示例：
输入：n = 3
输出：3
解释：

1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1

二、思路分析

这其实是一个典型的 斐波那契数列问题。

因为：

• 想到达第 n 阶，要么从 n-1 阶走一步上来；
• 要么从 n-2 阶走两步上来。

所以有状态转移公式：
f(n) = f(n - 1) + f(n - 2)

三、方法一：递归（不带记忆）

思路

用最直观的递归实现：

• 定义 f(n) 表示爬到第 n 阶的方法数
• 基础条件：
  • f(1) = 1
  • f(2) = 2
• 转移方程：
  • f(n) = f(n-1) + f(n-2)

C++代码

class Solution {public: int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); }};

四、方法二：递归 + 记忆化搜索（Top-Down DP）

思路

用一个数组 memo[n] 缓存每个子问题的答案

如果之前已经算过 f(n)，就不再递归，而是直接返回结果

C++代码

class Solution {public: int climbStairs(int n) { vector<int> memo(n + 1, -1); return helper(n, memo); } int helper(int n, vector<int>& 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]; }};

五、方法三：动态规划（Bottom-Up）

思路

直接从底向上计算

dp[i] 表示爬到第 i 阶的方法数

初始化：
dp[1] = 1
dp[2] = 2
dp[i] = dp[i - 1] + dp[i - 2] (i >= 3)
C++代码

class Solution {public: int climbStairs(int n) { if (n == 1) return 1; 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]; }};

六、方法四：动态规划 + 空间优化

思路

由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，我们可以只用两个变量滚动存储：

C++代码

class Solution {public: int climbStairs(int n) { if (n == 1) return 1; int first = 1, second = 2; for (int i = 3; i <= n; ++i) { int third = first + second; first = second; second = third; } return second; }};

总结

通过 LeetCode 第 70 题“Climbing Stairs”，我们完整经历了从暴力递归到记忆化搜索，再到动态规划及空间优化的整个算法进阶路径。这道看似简单的题目，实际上蕴含了递归思想、状态转移、子问题重叠、空间压缩等一系列动态规划核心理念。

掌握它，不仅有助于建立解决问题的框架思维，也为今后应对更复杂的 DP 问题打下基础。

推荐进一步挑战的题目：

• LeetCode 198. 打家劫舍（带状态转移）

• LeetCode 746. 使用最小花费爬楼梯（与本题模型相近）

• LeetCode 120. 三角形最小路径和（二维 DP）