宁妄爬楼梯问题是动态规划的经典入门题，咱们用 Python 实现时核心是抓住状态转移的逻辑～ 我来一步步拆解给你看：
问题描述
假设你需要爬 n 阶楼梯，每次可以爬 1 步或 2 步。问到达第 n 阶共有多少种不同的方法？
动态规划思路
动态规划的核心是「状态定义」和「状态转移」。
1. 状态定义
定义 dp[i] 为到达第 i 阶楼梯的方法数（即我们要求的答案）。
2. 状态转移
要到达第 i 阶楼梯，只有两种方式：
- 从第
i-1阶爬 1 步上来 → 方法数为dp[i-1] - 从第
i-2阶爬 2 步上来 → 方法数为dp[i-2]
因此，状态转移方程为：dp[i] = dp[i-1] + dp[i-2]
3. 初始条件
- 当
i=1时（只有 1 阶），只能爬 1 步 →dp[1] = 1 - 当
i=2时（有 2 阶），可以爬两次 1 步或一次 2 步 →dp[2] = 2
Python 代码实现
根据上面的思路，我们可以用迭代的方式计算（空间优化版，不需要保存整个数组）：
def climb_stairs(n: int) -> int:
if n <= 2:
return n # 边界条件：n=1返回1，n=2返回2
# 用两个变量滚动记录前两阶的方法数（优化空间）
prev, curr = 1, 2 # dp[1]=1, dp[2]=2
for i in range(3, n+1):
next_val = prev + curr # 计算当前阶的方法数
prev, curr = curr, next_val # 滚动更新前两阶的值
return curr
# 测试示例
print(climb_stairs(3)) # 输出3（1+1+1, 1+2, 2+1）
print(climb_stairs(4)) # 输出5（1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2）复杂度分析
- 时间复杂度：O(n)，只需遍历一次从 3 到 n 的楼梯阶数。
- 空间复杂度：O(1)，仅用了 3 个变量保存中间状态（优化后）。
扩展思考
如果题目改为「每次可以爬 1、2、…、k 步」，状态转移方程会变成 dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]（需注意边界条件）。这种情况下可以用滑动窗口或前缀和进一步优化～ 有兴趣的话可以试试扩展实现哦！ 😊
