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

状态与转移方程设计

状态与转移方程设计

动态规划最难的部分通常不是写循环,而是决定“数组中的每个位置究竟表示什么”。本课用一套可复用的四步方法,把状态含义、可选决策、转移来源和边界条件连成完整链路,并通过最小爬楼花费示例验证设计是否自洽。

学习目标

  • 能用一句精确、可验证的话定义动态规划状态。
  • 能从选择集合推导转移方程,并识别遗漏或重复的来源。
  • 能为状态设置边界条件、计算顺序和复杂度。

从问题描述提炼状态

状态是对“已经解决到什么程度”的压缩描述。一个合格状态必须同时说明阶段、约束和目标值。例如,dp[i] 不能只解释为“第 i 个位置的答案”,而应说明它覆盖的范围以及保存的是最小值、最大值、计数还是可行性。

设计状态时可以连续追问三个问题:当前已经处理到哪里;后续决策只需要依赖哪些历史信息;答案是否能由规模更小的同类状态组合得到。若某个定义仍需要回头查看大量原始决策,说明状态没有保存足够信息;若状态包含后续不再使用的细节,则可能导致维度过高。

检查项 合格描述 含糊描述
阶段 已到达位置 i 处理了一部分
约束 只能从前一阶或前两阶到达 按规则移动
目标值 到达 i 的最小累计花费 当前结果

四步设计法

  1. 定义状态:明确下标或多个维度分别代表什么,并写清状态值的语义。
  2. 枚举选择:列出从当前阶段出发允许采取的全部决策。
  3. 寻找来源:对每个选择确定它来自哪个更小状态,再用 min、max、求和或逻辑运算合并。
  4. 补齐边界:为最小规模状态赋值,并据此确定从前向后、从后向前或按区间长度计算。

动态规划状态与转移方程设计流程

示例:最小爬楼花费

给定数组 cost,其中 cost[i] 表示踩上第 i 阶需要支付的花费。每次可以向上走一阶或两阶,目标是到达楼梯顶部;顶部位于最后一阶之后,不需要额外付费。

定义 dp[i] 为“到达位置 i 的最小累计花费”。到达 i 只有两种来源:从 i - 1 踩过来并支付 cost[i - 1],或者从 i - 2 跨过来并支付 cost[i - 2]。因此转移为 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

起点允许站在位置 0 或位置 1,且尚未踩上任何阶梯,所以边界为 dp[0] = 0、dp[1] = 0。由于 dp[i] 只依赖更小下标,状态按 i 递增计算。

python
def min_climbing_cost(cost):
    n = len(cost)
    dp = [0] * (n + 1)

    # dp[i] 表示到达位置 i 的最小累计花费。
    for i in range(2, n + 1):
        from_previous = dp[i - 1] + cost[i - 1]
        from_two_steps_back = dp[i - 2] + cost[i - 2]
        dp[i] = min(from_previous, from_two_steps_back)

    return dp

if __name__ == "__main__":
    costs = [10, 15, 20, 5]
    states = min_climbing_cost(costs)

    print("dp =", states)
    print("minimum cost =", states[-1])

预期输出

text
dp = [0, 0, 10, 15, 20]
minimum cost = 20

验证方法与复杂度

先检查状态语义是否在每一行代码中保持一致,再检查所有合法来源是否都被枚举,最后用最小输入验证边界。例如,空数组和单元素数组都应直接得到 0,因为可以从顶部或第一阶位置开始。

该实现计算 n - 1 个状态,每个状态只比较两种来源,时间复杂度为 O(n),空间复杂度为 O(n)。由于转移只依赖前两个状态,也可以改用两个变量把额外空间降为 O(1),但首次推导时保留完整数组更便于检查状态变化。

常见错误

  • 状态定义缺少目标值:只写“到达第 i 阶”无法判断数组保存的是花费、方案数还是可行性。修复方式是把状态写成完整句子。
  • 转移来源与状态语义不一致:若 dp[i] 表示“到达位置 i”,就必须支付离开来源阶梯时对应的花费,不能误写成统一加 cost[i]。
  • 边界与起点规则冲突:把 dp[1] 设为 cost[0] 等价于强制从第 0 阶开始,会遗漏从第 1 阶直接起步的合法方案。

本课练习

设计“不能选择相邻元素的最大数组和”。要求先用一句话定义 dp[i],再列出选择第 i 个元素与不选择它的两种来源,给出空数组和单元素数组的边界,并实现一个能够处理负数输入的版本。验收时至少覆盖空数组、单元素数组和包含连续大数的数组。

本课总结

  • 状态必须同时表达阶段、约束和目标值,不能只描述下标。
  • 转移方程来自完整的选择集合,每个选择都要对应明确的前驱状态。
  • 边界条件决定最小问题的答案,依赖方向决定状态的计算顺序。

下一课预告

下一课将进入“背包问题”,把本课的状态与转移设计方法应用到容量约束下的取舍决策,并进一步学习二维状态压缩为一维数组时的遍历顺序。

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

目录与阅读设置

阅读设置

17

记录一个想法

状态与转移方程设计

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

登录哪都通