题目（含示例）

假设你正在爬楼梯。需要 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 阶

解题关键

1. 递推关系：到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数（因为最后一步只能是爬 1 阶或 2 阶）。
2. 初始条件：
   • 当 n=1 时，只有 1 种方法（直接爬 1 阶）。
   • 当 n=2 时，有 2 种方法（1+1 或 2）。
3. 空间优化：无需存储所有阶数的方法数，只需维护前两阶的结果即可（将空间复杂度从 O (n) 优化为 O (1)）。

解题代码

class Solution:
    def climbStairs(self, n: int) -> int:
        # 处理基本情况
        if n <= 2:
            return n
        
        # 初始化前两个台阶的方法数
        prev_prev = 1  # 第1阶的方法数
        prev = 2       # 第2阶的方法数
        
        # 从第3阶开始计算，直到第n阶
        for i in range(3, n + 1):
            current = prev_prev + prev
            prev_prev, prev = prev, current
        
        return prev
    

解题所需要掌握的基础知识

1. 递归与递推：理解 “当前结果依赖前序结果” 的逻辑（如 f (n) = f (n-1) + f (n-2)）。
2. 动态规划思想：通过分解问题为子问题，利用子问题的解推导原问题的解。
3. 迭代遍历：掌握 for 循环的基本使用，用于从基础情况逐步计算到目标值。
4. 变量赋值与更新：理解 Python 中 “多重赋值”（如 a, b = b, c）的语法，用于滚动更新变量。

该题对应的进阶知识

1. 时间复杂度优化：
   • 矩阵快速幂：将时间复杂度从 O (n) 优化至 O (log n)（利用矩阵 exponentiation by squaring 特性）。
   • 斐波那契通项公式：直接通过公式计算第 n 项（但存在浮点数精度问题）。
2. 动态规划空间优化：
   • 滚动数组思想：对于依赖前 k 个状态的问题，可仅用 k 个变量存储中间结果（如本题依赖前 2 个状态，用 2 个变量即可）。
3. 扩展问题：
   • 允许爬 1、2、...、k 个台阶时的解法（递推关系变为 f (n) = f (n-1) + f (n-2) + ... + f (n-k)）。
   • 带约束条件的爬楼梯（如某些台阶不能踩）。

解题思路总结

1. 问题分析：爬楼梯的方法数由 “最后一步爬 1 阶” 或 “最后一步爬 2 阶” 两种情况组成，因此可分解为子问题。
2. 递推公式推导：基于子问题关系，得到 f (n) = f (n-1) + f (n-2)，其中 f (1)=1，f (2)=2。
3. 实现优化：
   • 避免使用递归（递归会导致重复计算，时间复杂度 O (2ⁿ)）。
   • 不使用数组存储所有结果（节省空间，改用两个变量滚动更新）。
4. 迭代计算：从 n=3 开始，通过循环逐步计算到第 n 阶，最终返回结果。

该思路通过动态规划和空间优化，高效解决了问题，兼顾时间和空间效率。