数据结构与算法 / 系统课时

从暴力递归推导状态转移

从暴力递归推导状态转移

状态转移并不是凭空猜出的公式。更可靠的方法是先写出“把所有选择都试一遍”的递归,让函数参数自然暴露子问题,再观察递归调用之间的关系。本节用爬楼梯问题把暴力递归逐步改写成明确的 DP 状态与迭代计算。

学习目标

  • 从递归函数的参数中识别动态规划状态
  • 从递归调用关系提炼状态转移与边界条件
  • 把指数级重复递归改写成自底向上的线性计算

从枚举所有选择开始

假设有 n 级台阶,每次只能走 1 级或 2 级,求到达顶部的走法数量。先不考虑效率,只描述所有合法选择:如果当前还剩 n 级,那么第一步要么走 1 级,留下规模为 n-1 的子问题;要么走 2 级,留下规模为 n-2 的子问题。

因此可以把 f(n) 定义为“走完剩余 n 级台阶的方法数”。当 n=0 时已经到达顶部,只有 1 种完成方式;当 n=1 时也只有走 1 级这一种方式。递归关系自然得到 f(n) = f(n - 1) + f(n - 2)。

爬楼梯暴力递归中的重复子问题

递归树暴露了一个重要事实:路径不同,但只要剩余台阶数相同,后续答案就相同。于是“如何走到这里”可以被丢弃,只保留 n 这一项状态。

把递归参数变成状态

推导状态时,先问递归函数需要哪些参数才能独立回答问题。在这个例子中,函数只需要知道剩余台阶数 n,因此 DP 只需要一维状态。若递归函数还需要位置、容量、是否使用过某个机会等信息,这些参数通常都会成为候选状态维度。

接着把递归调用翻译成转移。递归中的“调用 f(n-1) 和 f(n-2) 后相加”,直接对应 DP 中“当前状态由前两个状态相加”。边界条件同样来自递归终止条件,而不是为了让数组不越界临时补出来。

这里可以得到三个完整组成部分:状态含义是 f(n) 表示走完 n 级台阶的方法数;边界是 f(0)=1、f(1)=1;转移是 f(n)=f(n-1)+f(n-2)。只要这三项彼此一致,记忆化和迭代写法只是计算顺序不同。

改写为自底向上计算

下面的完整程序同时保留暴力递归和迭代 DP,便于验证两种写法得到相同答案。递归版本直接表达选择关系,迭代版本按照状态依赖顺序只计算每个状态一次。

python
def ways_recursive(n: int) -> int:
    if n <= 1:
        return 1
    # 两个分支分别对应第一步走 1 级和走 2 级。
    return ways_recursive(n - 1) + ways_recursive(n - 2)


def ways_dp(n: int) -> int:
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    # 当前状态只依赖已经计算完成的前两个状态。
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


n = 5
print(f"recursive: {ways_recursive(n)}")
print(f"dp: {ways_dp(n)}")

预期输出

text
recursive: 8
dp: 8

实际运行时这里没有动态时间、端口或路径值,因此输出是确定的。两种实现结果一致,说明状态定义、边界条件和转移关系至少在该输入上保持一致。

为什么复杂度会下降

暴力递归会反复计算相同的 f(k)。它的调用树规模随 n 指数增长,时间复杂度通常记为 O(2n)O(2^n) 的量级;迭代 DP 只计算 f(0) 到 f(n) 各一次,因此时间复杂度降为 O(n)O(n),数组版本的空间复杂度也是 O(n)O(n)。

由于当前状态只依赖前两个状态,还可以继续把数组压缩成两个变量,将额外空间降到 O(1)O(1)。不过空间优化应放在状态转移已经正确之后,否则过早覆盖旧状态会让依赖关系更难检查。

推导时优先检查三个位置

第一,状态含义必须稳定。如果一会儿把 dp[i] 解释为“到达第 i 级的方法数”,一会儿又解释为“还剩 i 级的方法数”,边界和转移很容易错位。

第二,边界应来自原问题的最小可解子问题。不要只为了让示例输出正确而猜 dp[0],应解释清楚空剩余步骤为什么对应一种完成方式。

第三,迭代顺序必须满足依赖关系。当 dp[i] 依赖更小下标时从小到大计算;若状态转移依赖尚未计算的状态,就需要重新考虑遍历顺序、状态定义或计算方式。

从暴力递归推导 DP 的核心动作,就是把“递归函数参数”变成状态,把“递归调用”变成转移,把“递归终止条件”变成边界,再消除重复计算。这样得到的状态转移有来源,也更容易验证。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

从暴力递归推导状态转移

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通