Hello 算法动态规划入门：从爬楼梯看暴力搜索、记忆化搜索到状态转移方程

本篇基于 《Hello 算法》动态规划章节的"初探动态规划"文档，以"爬楼梯"这一经典例题为载体，完整还原了从暴力回溯、暴力搜索、记忆化搜索到底至顶动态规划（含空间优化）的渐进式推导过程。读完本文，你将掌握动态规划的三个核心概念——dp 表、初始状态、状态转移方程，并能结合仓库中 Python、Java、C 等多语言源码验证每一版解法的实现细节，理解"滚动数组"这一通用空间优化技巧的适用条件。

问题定义：爬楼梯

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

如上图所示，对于一个 $3$ 阶楼梯，共有 $3$ 种方案可以爬到楼顶：(1, 1, 1)、(1, 2)、(2, 1)。

动态规划是一个重要的算法范式，它将一个问题的解分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。下面仓库中的多语言代码以 $n = 9$ 作为驱动输入（各语言 Driver Code 中均设置 n = 9），可以直观对比各解法的结果一致性。

方法零：回溯穷举所有方案

本题的目标是求解方案数量，我们可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上 $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]

几个值得注意的实现细节：

• 剪枝条件：state + choice > n 时跳过该分支，即不允许越过第 $n$ 阶；
• 计数方式：使用列表 res[0] 而非局部变量记录方案数，这是在 Python 中跨递归层修改计数的常用手法；
• 同样的回溯骨架在 Java 版、C 版 以及仓库其他十余种语言实现中保持一致，便于跨语言对照阅读。

回溯算法通常并不显式地对问题进行拆解，而是将求解问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。它的正确性没有问题，但效率问题会引出后面的优化路径。

方法一：暴力搜索——从问题分解看递推关系

接下来尝试从问题分解的角度分析这道题。设爬到第 $i$ 阶共有 $dp[i]$ 种方案，那么 $dp[i]$ 就是原问题，其子问题包括：

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

由于每轮只能上 $1$ 阶或 $2$ 阶，因此当我们站在第 $i$ 阶楼梯上时，上一轮只可能站在第 $i - 1$ 阶或第 $i - 2$ 阶上。换句话说，我们只能从第 $i - 1$ 阶或第 $i - 2$ 阶迈向第 $i$ 阶。

由此便可得出一个重要推论：爬到第 $i - 1$ 阶的方案数加上爬到第 $i - 2$ 阶的方案数就等于爬到第 $i$ 阶的方案数，即状态转移方程：

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

这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。

根据递推公式可以得到暴力搜索解法：以 $dp[n]$ 为起始点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题 $dp[1]$ 和 $dp[2]$ 时返回。其中，最小子问题的解是已知的，即 $dp[1] = 1$、$dp[2] = 2$，表示爬到第 $1$、$2$ 阶分别有 $1$、$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$，则会陷入漫长的等待之中。

观察上图可以发现：指数阶的时间复杂度是"重叠子问题"导致的。例如 $dp[9]$ 被分解为 $dp[8]$ 和 $dp[7]$，$dp[8]$ 又被分解为 $dp[7]$ 和 $dp[6]$，两者都包含子问题 $dp[7]$。以此类推，子问题中包含更小的重叠子问题，子子孙孙无穷尽也——绝大部分计算资源都浪费在这些重叠的子问题上。

方法二：记忆化搜索——让每个重叠子问题只算一次

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝：

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] * (n + 1) 初始化，-1 表示"无记录"。这个约定依赖于本题方案数恒为正整数的性质，若子问题的解本身可能为负值或含 $0$ 作为合法解，就需要改用标记集合或其他判空方式；
• 先查缓存后计算：if mem[i] != -1: return mem[i] 这一行就是剪枝的核心，命中缓存时直接截断递归。

经过记忆化处理后，所有重叠子问题都只需计算一次，时间复杂度优化至 $O(n)$，这是一个巨大的飞跃。空间上，递归栈深度为 $O(n)$，mem 数组占 $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]

在 C 语言实现 中可以看到无垃圾回收环境下的对应写法：dp 表通过 malloc((n + 1) * sizeof(int)) 手动分配，并在返回结果前 free(dp) 释放，语义与 Python 版完全一致；Java 实现 则直接使用 int[] 数组。各语言的代码结构均严格遵循"初始化 dp 表 → 填充初始状态 → 循环状态转移"三步，便于对照学习。

与回溯算法一样，动态规划也使用"状态"概念来表示问题求解的特定阶段，每个状态都对应一个子问题以及相应的局部最优解。例如，爬楼梯问题的状态定义为当前所在楼梯阶数 $i$。

动态规划的三个核心术语

根据以上内容，可以总结出动态规划的常用术语：

• dp 表：数组 dp 本身称为 dp 表，$dp[i]$ 表示状态 $i$ 对应子问题的解；
• 初始状态：最小子问题对应的状态（爬楼梯中即第 $1$ 阶和第 $2$ 阶楼梯，对应 dp[1] = 1, dp[2] = 2）；
• 状态转移方程：递推公式 $dp[i] = dp[i-1] + dp[i-2]$，描述了如何由较小子问题的解推导较大子问题的解。

这三者恰好对应了上述代码的三个部分：dp = [0] * (n + 1) 建立 dp 表、dp[1], dp[2] = 1, 2 设置初始状态、for 循环内的赋值实现状态转移。这一"定义状态 → 确定初始状态 → 写出状态转移方程"的分析框架，是动态规划问题的一般求解路径，也是本仓库后续章节（如背包问题、编辑距离）所沿用的统一范式。

空间优化：滚动数组

细心的读者可能发现了：由于 $dp[i]$ 只与 $dp[i-1]$ 和 $dp[i-2]$ 有关，因此我们无须使用一个数组 dp 来存储所有子问题的解，而只需两个变量滚动前进即可。同一文件中的 climbing_stairs_dp_comp 函数给出了空间优化版：

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

变量 a、b 在每轮迭代中滚动承接 dp[i-2] 与 dp[i-1] 的角色，a, b = b, a + b 一行完成"取旧值、算新值、前移"三个动作。C 语言版 climbingStairsDPComp 则借助临时变量 tmp 显式完成同样的交换，因为 C 没有元组赋值语法。

由于省去了数组 dp 占用的空间，空间复杂度从 $O(n)$ 降至 $O(1)$。在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时可以只保留必要的状态，通过"降维"来节省内存空间。这种空间优化技巧被称为"滚动变量"或"滚动数组"。

需要注意其适用前提：只有当状态转移方程中引用的历史状态窗口有限（如本题只依赖前 2 个状态），且后续不再需要查询任意中间 $dp[k]$ 的值时，滚动数组才成立；若转移方程依赖距离较远或不定的历史状态，就只能保留完整 dp 表。

四种解法的复杂度对比

以 $n = 9$ 为例（各语言 Driver Code 均取此输入），四种解法结果一致为 $34$ 种方案，但计算代价差异显著：

解法	代表实现	时间复杂度	空间复杂度	关键手段
回溯穷举	climbing_stairs_backtrack.py	$O(2^n)$	$O(n)$（递归栈）	选择-尝试-回退
暴力搜索	climbing_stairs_dfs.py	$O(2^n)$	$O(n)$（递归栈）	递归分解，存在重叠子问题
记忆化搜索	climbing_stairs_dfs_mem.py	$O(n)$	$O(n)$	mem 数组剪枝重叠子问题
动态规划	climbing_stairs_dp.py	$O(n)$	$O(n)$，优化后 $O(1)$	自底向上迭代 + 滚动数组

从这组演进路径可以提炼出动态规划的本质：它并非一种孤立的算法技巧，而是对"具有重叠子问题与最优子结构性质"的递归问题的系统性加速——先写出朴素递归，再识别重叠，最后用记忆（自顶向下）或迭代（自底向上）消除重复计算，视状态依赖窗口决定能否滚动数组省空间。掌握这条"暴力 → 优化"的推导链后，读者即可沿用本仓库 动态规划章节 后续篇目（如 dp 问题求解流程）中更复杂的背包、编辑距离等问题的同一套分析方法。