爬楼梯问题

题目

爬楼梯问题

信息

• 类型：问答
• 难度：⭐

考点

动态规划基础,状态转移方程,边界条件处理

快速回答

使用动态规划解决爬楼梯问题：

• 定义状态：dp[i] 表示爬到第 i 阶楼梯的方法数
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
• 边界条件：dp[0] = 1, dp[1] = 1
• 时间复杂度：O(n)，空间复杂度：O(n)（可优化为 O(1)）

问题描述

假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。求有多少种不同的方法可以爬到楼顶？（n 为正整数）

原理说明

动态规划的核心思想是将大问题分解为重叠子问题：

• 最优子结构：到达第 i 阶的方法数取决于第 i-1 阶和第 i-2 阶的方法数
• 状态定义：dp[i] 表示到达第 i 阶楼梯的方案总数
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
  （因为最后一步可能是跨 1 阶或 2 阶）
• 边界条件：
  dp[0] = 1（起点方案数为1）
  dp[1] = 1（爬1阶只有1种方法）

代码示例（Python）

def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 空间优化版（O(1)空间）
def climb_stairs_optimized(n: int) -> int:
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

最佳实践

• 边界处理：单独处理 n=0 和 n=1 的情况
• 空间优化：只需两个变量滚动存储状态（斐波那契数列）
• 测试用例：
  n=2 → 2种（1+1 或 2）
  n=3 → 3种（1+1+1, 1+2, 2+1）

常见错误

• 错误转移方程：写成 dp[i] = dp[i-1] + 1（未考虑跨2阶方案）
• 边界值错误：设置 dp[0]=0 导致结果偏小
• 索引越界：未处理 n=0 时 dp[1] 的访问越界

扩展知识

• 斐波那契数列：本题本质是求斐波那契数列第 n+1 项
• 变种问题：
  1. 每次可爬 1/2/3 阶 → dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
  2. 有障碍物（LeetCode 70 进阶版）
  3. 最小花费爬楼梯（LeetCode 746）
• 数学解法：通项公式或矩阵快速幂（O(log n) 时间复杂度）