上台阶问题简介

上台阶问题是一个经典的动态规划问题。它描述了一个人爬楼梯的方式：每次可以爬1级或2级台阶，问有多少种不同的方法可以爬到楼顶？

假设楼梯总共有 n 级台阶，那么这个问题可以通过递归或者动态规划来解决。

---

📌 问题描述

给定一个正整数 n 表示楼梯的台阶总数，每次你可以选择爬1级或者2级台阶，问有多少种不同的方法可以爬到楼顶？

示例：

• 如果 n = 2，则有两种方法：
  • 方法1：一步一级台阶，共两次
  • 方法2：一步两级台阶，仅一次
• 如果 n = 3，则有三种方法：
  • 方法1：1 + 1 + 1
  • 方法2：1 + 2
  • 方法3：2 + 1

---

🧠 解决思路

动态规划（推荐）

我们可以使用动态规划的方法来解决这个问题。设 dp[i] 表示到达第 i 级台阶的不同方法数，则有以下递推关系：

dp[i] = dp[i-1] + dp[i-2]

这是因为要到达第 i 级台阶，可以从第 i-1 级台阶走一步上来，也可以从第 i-2 级台阶走两步上来。

初始条件：

• dp[0] = 1：表示地面（0级台阶）有一种方式到达（即不动）
• dp[1] = 1：表示只有1级台阶时只有一种方式到达（即直接走上去）

优化空间复杂度

由于每次计算只需要前两个状态，所以不需要维护整个数组，只需用两个变量即可。

---

📦 Python 实现

方法一：动态规划（完整数组）

def climbStairs(n: int) -> int:
    if n == 0:
        return 1
    elif n == 1:
        return 1
    
    # 初始化dp数组
    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]

# 示例
print(climbStairs(2))  # 输出: 2
print(climbStairs(3))  # 输出: 3
print(climbStairs(5))  # 输出: 8

方法二：优化空间复杂度

由于我们只需要前两个状态值，因此可以只用两个变量来存储这些值，从而减少空间复杂度。

def climbStairsOptimized(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    
    prev1, prev2 = 1, 1  # dp[0] 和 dp[1]
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

# 示例
print(climbStairsOptimized(2))  # 输出: 2
print(climbStairsOptimized(3))  # 输出: 3
print(climbStairsOptimized(5))  # 输出: 8

方法三：递归（带记忆化）

虽然递归方法直观易懂，但如果不加优化会导致大量的重复计算。因此，可以使用记忆化技术来避免重复计算。

from functools import lru_cache

@lru_cache(None)
def climbStairsRecursive(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2)

# 示例
print(climbStairsRecursive(2))  # 输出: 2
print(climbStairsRecursive(3))  # 输出: 3
print(climbStairsRecursive(5))  # 输出: 8

---

💡 扩展练习

练习1：用户输入台阶数

编写程序让用户输入台阶数，并输出不同的爬法数量。

def main():
    n = int(input("请输入台阶总数: "))
    print(f"爬上 {n} 级台阶的不同方法数是: {climbStairsOptimized(n)}")

if __name__ == "__main__":
    main()

练习2：增加异常处理

确保用户输入的是有效的正整数，并给出错误提示。

def get_input(prompt):
    while True:
        try:
            value = int(input(prompt))
            if value < 0:
                raise ValueError
            break
        except ValueError:
            print("无效输入，请输入一个非负整数！")
    return value

def main():
    n = get_input("请输入台阶总数: ")
    print(f"爬上 {n} 级台阶的不同方法数是: {climbStairsOptimized(n)}")

if __name__ == "__main__":
    main()

练习3：不同步长的扩展

假设每步可以走1级、2级或3级台阶，修改代码以适应这种情况。

def climbStairsWithSteps(n: int) -> int:
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n == 2:
        return 2  # 两种情况：1+1 或 2
    
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    
    return dp[n]

# 示例
print(climbStairsWithSteps(4))  # 输出: 7

---

📋 总结

通过本教程，你应该能够：

• 使用动态规划解决上台阶问题。
• 编写程序接收用户输入并进行异常处理。
• 理解如何优化算法以提高效率和减少空间占用。
• 扩展问题以适应更多种步长的情况。

如果你希望进一步了解以下内容，请告诉我：

✅ 如何处理更复杂的步长组合？
✅ 更复杂的递归/迭代问题示例及解析？
✅ 动态规划在其他经典问题中的应用？

我可以为你提供更详细的指导或定制化的代码示例 😊

---

示例运行结果

对于 n = 5 的情况：

爬上 5 级台阶的不同方法数是: 8

这意味着有8种不同的方法可以爬上5级台阶。