Hello 算法动态规划入门：以爬楼梯问题讲透回溯、记忆化搜索与状态转移方程

本文基于《Hello 算法》仓库中「Introduction to Dynamic Programming」章节内容，以经典的「爬楼梯」问题为线索，从回溯暴力枚举出发，逐步推导出递推关系、记忆化搜索、自底向上的动态规划写法以及空间优化（滚动变量）的完整思路。读完本文，你不仅能掌握 dp 表、初始状态、状态转移方程等动态规划核心术语，还能在仓库中找到对应源码直接运行验证。

问题定义：一次只能爬 1 阶或 2 阶的楼梯

原文档给出了一个经典的入门问题：

!!! question "爬楼梯" 给定一个共有 $n$ 级台阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶？

例如对 3 阶楼梯而言，一共有 3 种不同走法。之所以要先从这类问题入手，是因为它足够简单，却同时具备动态规划问题的全部关键特征：多阶段决策、子问题重叠、状态可递推。

原文档说明：本题求的是「方案数量」，因此天然适合用回溯（backtracking）枚举所有可能。把爬楼想象成多轮选择——从地面出发，每轮选择上 1 阶或 2 阶，到达楼顶时计数加 1，超过楼顶则剪枝。仓库中的回溯实现位于 climbing_stairs_backtrack.py：

def backtrack(choices: list[int], state: int, n: int, res: list[int]) -> int:
    """回溯"""
    # 当爬到第 n 阶时，方案数量加 1
    if state == n:
        res[0] += 1
    # 遍历所有选择
    for choice in choices:
        # 剪枝：不允许越过第 n 阶
        if state + choice > n:
            continue
        # 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res)
        # 回退


def climbing_stairs_backtrack(n: int) -> int:
    """爬楼梯：回溯"""
    choices = [1, 2]  # 可选择向上爬 1 阶或 2 阶
    state = 0  # 从第 0 阶开始爬
    res = [0]  # 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res)
    return res[0]

注意到 res 被写成单元素列表，是为了在递归回溯中跨作用域累加计数。这一步的定位很明确：回溯算法通常不显式拆分问题，而是把求解视为「一系列决策步骤」，通过尝试与剪枝搜索全部可行解。

从暴力枚举到递推关系：发现状态转移方程

如果从「问题分解」的角度重新审视，可以得到更本质的结构。记爬到第 $i$ 阶的方案数为 $dp[i]$，那么原问题 $dp[n]$ 的子问题集合是：

$$dp[i-1], dp[i-2], \dots, dp[2], dp[1]$$

关键观察在于：每轮只能上 1 阶或 2 阶，因此站在第 $i$ 阶时，上一轮只可能站在第 $i-1$ 阶或第 $i-2$ 阶——也就是说，爬到第 $i$ 阶的方案数，等于爬到第 $i-1$ 阶的方案数与爬到第 $i-2$ 阶的方案数之和：

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

这就是本题的状态转移方程。下图直观展示了这一递推结构。

最小子问题的解是已知的初始条件：$dp[1] = 1$、$dp[2] = 2$，分别表示爬到第 1、2 阶各有 1 种、2 种走法（与上图中「3 阶共 3 种」互相印证：$dp[3]=dp[2]+dp[1]=3$）。

方法一：纯递归暴力搜索

有了递推公式后，最直接的写法是自顶向下递归分解：从 $dp[n]$ 出发，把一个大问题递归拆成两个更小的子问题之和，直到触及最小子问题 $dp[1]$、$dp[2]$ 再返回。它与标准回溯一样使用深度优先搜索，但代码更简洁。仓库实现位于 climbing_stairs_dfs.py：

def dfs(i: int) -> int:
    """搜索"""
    # 已知 dp[1] 和 dp[2] ，返回之
    if i == 1 or i == 2:
        return i
    # dp[i] = dp[i-1] + dp[i-2]
    count = dfs(i - 1) + dfs(i - 2)
    return count


def climbing_stairs_dfs(n: int) -> int:
    """爬楼梯：搜索"""
    return dfs(n)

这种写法的调用结构是一棵递归树。对 $dp[n]$ 而言，递归树深度为 $n$，时间复杂度为 $O(2^n)$——指数级增长极其迅速，当 $n$ 稍大时等待时间会难以接受。

罪魁祸首：重叠子问题

指数级时间复杂度的根源在于重叠子问题（overlapping subproblems）。以 $dp[9]$ 为例：它被拆成 $dp[8]$ 与 $dp[7]$，而 $dp[8]$ 又会被拆成 $dp[7]$ 与 $dp[6]$——两个分支里都出现了 $dp[7]$。层层嵌套下去，子问题内部又包含更小的重叠子问题，海量算力被白白浪费在了重复计算上。这正是动态规划所要解决的核心矛盾。

方法二：记忆化搜索（自顶向下）

要让所有重叠子问题只计算一次，办法是引入一张记录表。原文档给出了两条规则：

1. 首次算出 $dp[i]$ 时，把它记入 mem[i] 备用；
2. 之后再次需要 $dp[i]$ 时，直接从 mem[i] 读取结果，避免重复递归。

仓库实现位于 climbing_stairs_dfs_mem.py：

def dfs(i: int, mem: list[int]) -> int:
    """记忆化搜索"""
    # 已知 dp[1] 和 dp[2] ，返回之
    if i == 1 or i == 2:
        return i
    # 若存在记录 dp[i] ，则直接返回之
    if mem[i] != -1:
        return mem[i]
    # dp[i] = dp[i-1] + dp[i-2]
    count = dfs(i - 1, mem) + dfs(i - 2, mem)
    # 记录 dp[i]
    mem[i] = count
    return count


def climbing_stairs_dfs_mem(n: int) -> int:
    """爬楼梯：记忆化搜索"""
    # mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    mem = [-1] * (n + 1)
    return dfs(n, mem)

mem 用 -1 表示「尚未计算」，与合法的方案数值天然区分。加入记忆化后，所有重叠子问题至多被完整求解一次，时间复杂度从 $O(2^n)$ 锐降到 $O(n)$——这是数量级的飞跃。

方法三：真正的动态规划（自底向上）

原文档用一个关键视角区分了两种优化路线：

• 记忆化搜索是"自顶向下"：从原问题（根节点）出发，把大问题递归拆成小问题，触底到已知的最小问题（叶节点）后，再通过回溯逐层汇总，拼出原问题的解。
• 动态规划是"自底向上"：直接从最小子问题的解出发，用循环迭代逐级构造更大的子问题，直至得到原问题。

由于没有回溯过程，动态规划只需循环迭代、不需要递归。代码里同样声明一个数组 dp 存放子问题的解——它起到的记录作用与记忆化里的 mem 完全一致。仓库实现位于 climbing_stairs_dp.py：

def climbing_stairs_dp(n: int) -> int:
    """爬楼梯：动态规划"""
    if n == 1 or n == 2:
        return n
    # 初始化 dp 表，用于存储子问题的解
    dp = [0] * (n + 1)
    # 初始状态：预设最小子问题的解
    dp[1], dp[2] = 1, 2
    # 状态转移：从较小子问题逐步求解较大子问题
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

数组下标 $0$ 未被使用，仅为了与台阶编号 $1..n$ 对齐、便于书写 dp[i-1]、dp[i-2]。这版代码的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

与回溯一致，动态规划同样用「状态（state）」刻画求解过程中的特定阶段——每个状态对应一个子问题及其局部最优解；在爬楼梯问题里，状态就是当前的台阶编号 $i$。

术语小结

顺着上面的推导，可以正式给出动态规划的核心术语（对应原文档「Method 3」末尾的总结）：

• dp 表（dp table）：即数组 dp，其中 $dp[i]$ 表示状态 $i$ 对应子问题的解；
• 初始状态（initial states）：最小子问题（第 1、2 阶）对应的状态，其解已知且直接预设；
• 状态转移方程（state transition equation）：递推式 $dp[i] = dp[i-1] + dp[i-2]$，描述状态之间如何迁移。

空间优化：滚动变量把 $O(n)$ 降到 $O(1)$

细心的读者会发现：$dp[i]$ 只与 $dp[i-1]$、$dp[i-2]$ 相关，因此根本不必用整张数组存下所有子问题，只需两个向前滚动的变量即可。仓库在同一文件 climbing_stairs_dp.py 中给出了压缩版本：

def climbing_stairs_dp_comp(n: int) -> int:
    """爬楼梯：空间优化后的动态规划"""
    if n == 1 or n == 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

去掉 dp 数组占用的空间后，空间复杂度由 $O(n)$ 降至 $O(1)$，时间复杂度仍为 $O(n)$。

这一步背后的方法论值得单独强调：在动态规划问题中，当前状态往往只依赖有限个前驱状态，此时可以只保留必要状态、通过「降维」节省内存。这种空间优化技巧统称为"滚动变量（rolling variable）"或"滚动数组（rolling array）"，它在很多 DP 题目（如背包、路径计数）中都能复用。

复杂度对比与仓库延伸阅读

将四步推导的复杂度归纳如下（依据本仓库英文版 en/docs/chapter_dynamic_programming/intro_to_dynamic_programming.md 及其对应源码推导）：

方法	代表函数	时间复杂度	空间复杂度	特点
回溯枚举	climbing_stairs_backtrack	$O(2^n)$	$O(n)$（递归栈）	决策 + 剪枝，最直观
递归暴力	climbing_stairs_dfs	$O(2^n)$	$O(n)$（递归栈）	显式递推但重叠子问题重复计算
记忆化搜索	climbing_stairs_dfs_mem	$O(n)$	$O(n)$	自顶向下 + 查表剪枝
动态规划	climbing_stairs_dp	$O(n)$	$O(n)$	自底向上循环迭代
空间优化 DP	climbing_stairs_dp_comp	$O(n)$	$O(1)$	滚动变量压缩

如果想在本地运行验证，Python 各实现自带 Driver Code，直接执行即可，例如：

python3 codes/python/chapter_dynamic_programming/climbing_stairs_dp.py

同一主题在仓库中还有多语言实现（如 Java 版 climbing_stairs_dp.java，C、C++、Go、Rust、JavaScript、TypeScript 等均位于 codes 对应语言目录下），函数逻辑与 Python 版一一对应，适合对照阅读不同语言的写法差异。

进阶读者可以继续阅读本章后续内容，把今天学到的方法论应用到更复杂的场景：

• dp_problem_features.md：什么特征的问题适合用 DP（最优子结构、无后效性）；
• dp_solution_pipeline.md：从问题建模、状态定义到转移方程的完整解题流程；
• 仓库中的 climbing_stairs_constraint_dp.py 与 min_cost_climbing_stairs_dp.py：同一个爬楼梯模型加入了「禁止连爬两步」「带代价」等约束后的变体。

爬楼梯问题虽小，却是理解动态规划本质的最佳切片：从回溯里看见重叠子问题，用记忆化消灭重复计算，借自底向上去掉递归栈，再用滚动数组榨干多余空间——这条从 $O(2^n)$ 到 $O(n)$ 的优化路径，正是绝大多数动态规划题目的通用思考模板。