数据结构与算法 / 系统课时
状态与转移方程设计
状态与转移方程设计
动态规划最难的部分通常不是写循环,而是决定“数组中的每个位置究竟表示什么”。本课用一套可复用的四步方法,把状态含义、可选决策、转移来源和边界条件连成完整链路,并通过最小爬楼花费示例验证设计是否自洽。
学习目标
- 能用一句精确、可验证的话定义动态规划状态。
- 能从选择集合推导转移方程,并识别遗漏或重复的来源。
- 能为状态设置边界条件、计算顺序和复杂度。
从问题描述提炼状态
状态是对“已经解决到什么程度”的压缩描述。一个合格状态必须同时说明阶段、约束和目标值。例如,dp[i] 不能只解释为“第 i 个位置的答案”,而应说明它覆盖的范围以及保存的是最小值、最大值、计数还是可行性。
设计状态时可以连续追问三个问题:当前已经处理到哪里;后续决策只需要依赖哪些历史信息;答案是否能由规模更小的同类状态组合得到。若某个定义仍需要回头查看大量原始决策,说明状态没有保存足够信息;若状态包含后续不再使用的细节,则可能导致维度过高。
| 检查项 | 合格描述 | 含糊描述 |
|---|---|---|
| 阶段 | 已到达位置 i |
处理了一部分 |
| 约束 | 只能从前一阶或前两阶到达 | 按规则移动 |
| 目标值 | 到达 i 的最小累计花费 |
当前结果 |
四步设计法
- 定义状态:明确下标或多个维度分别代表什么,并写清状态值的语义。
- 枚举选择:列出从当前阶段出发允许采取的全部决策。
- 寻找来源:对每个选择确定它来自哪个更小状态,再用
min、max、求和或逻辑运算合并。 - 补齐边界:为最小规模状态赋值,并据此确定从前向后、从后向前或按区间长度计算。

示例:最小爬楼花费
给定数组 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 递增计算。
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])预期输出
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 个元素与不选择它的两种来源,给出空数组和单元素数组的边界,并实现一个能够处理负数输入的版本。验收时至少覆盖空数组、单元素数组和包含连续大数的数组。
本课总结
- 状态必须同时表达阶段、约束和目标值,不能只描述下标。
- 转移方程来自完整的选择集合,每个选择都要对应明确的前驱状态。
- 边界条件决定最小问题的答案,依赖方向决定状态的计算顺序。
下一课预告
下一课将进入“背包问题”,把本课的状态与转移设计方法应用到容量约束下的取舍决策,并进一步学习二维状态压缩为一维数组时的遍历顺序。