动态规划 · HTML
数学 / 逻辑形态
dp[i] 表示前 i 项或以 i 结尾的最优值/方案数。转移 dp[i]=Aggregate(dp[j], local(j,i))，其中 j 来自有限邻域或所有 j<i；初始化空前缀/首项。
识别信号
- 输入是一维序列或时间线。
- 答案可按前缀推进，后缀只关心前缀摘要。
- 同一前缀状态会被多条决策路径重复到达。
- 当前决策依赖前一项或少量早期位置。
- 问题问最优值、可行性或方案数而非具体枚举。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 局部选择可交换 | 若能证明单一局部规则永不后悔，贪心更简洁；DP 用于多个历史分支需保留。 |
| 状态其实需要集合 | 若未来依赖已选元素集合，单个 i 不充分，需 bitmask 或更丰富状态。 |
| 只需固定窗口统计 | 若没有选择重叠子问题，滑动窗口/前缀和更合适。 |
核心不变量
计算完 i 后，所有不超过 i 的状态都等于其定义下的真实最优值/计数；任何未来转移只读取这些已完成状态。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 位置/前缀索引与未来真正需要的最小摘要；可另存 parent 恢复方案。 |
| Transition | 枚举最后一步来自哪些已完成状态，将局部贡献与子答案组合，再按 min/max/sum/or 聚合。 |
| Frontier / order | 按依赖拓扑从左到右的下一个索引；若只依赖固定数量前态，可滚动压缩。 |
Python 骨架
def min_linear_cost(cost):
n = len(cost)
if n == 0: return 0
if n == 1: return cost[0]
prev2, prev1 = cost[0], cost[1]
for i in range(2, n):
cur = cost[i] + min(prev1, prev2)
prev2, prev1 = prev1, cur
return min(prev1, prev2)
正确性思路
- base states 直接覆盖最小规模。
- 假设此前状态符合定义；任一到达 i 的完整方案都有一个被枚举的最后前态。
- 取这些完备候选的正确聚合得到 dp[i]；归纳到答案状态。
复杂度
| Time | Space | Parameters |
|---|
| O(n·d)，d 为每态检查的前驱数；固定 d 时 O(n) | O(n)；固定依赖可压缩到 O(d) | n 为序列长，d 为转移入度。 |
边界条件
- 空序列
- 长度 1/2
- 负值改变 base 语义
- 计数溢出或取模
- 答案是 dp[n] 还是若干尾态聚合
错误模式
| Pattern | Why it fails / fix |
|---|
| 先写递推再定义状态 | dp[i] 是前 i 项还是以 i 结尾会改变下标、base 与答案。 |
| 覆盖尚需的旧状态 | 滚动压缩前先画依赖，更新顺序必须保留所有前驱。 |
| base case 偷带决策 | 初始化必须与状态定义一致，不能靠样例凑值。 |
| 只返回最后一格 | 有些目标可在多个尾状态结束，需要再聚合。 |
选择与排除规则
- 先用一句话精确定义 dp[i]。
- 从‘最后一步’反推所有前驱。
- 确定依赖拓扑后再选迭代方向。
- 正确后才做滚动压缩，并保留 parent 若需恢复路径。
相关模板
| Relation | Template | Boundary |
|---|
| optimization | 单调队列维护窗口极值 | 转移从一个滑动前驱区间取极值。 |
| DAG 顺序组合 | 拓扑排序 / 入度消除 | 当 DP 状态形成一般 DAG 时，用拓扑序提供合法计算顺序；普通线性 DP 不需要先学拓扑排序。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最小总成本为 min(1,7)=1，说明答案未必是最后状态。 |
| Setup | 三段路费 [4,1,6]，可从前两段任一处起步，每次前进 1 或 2 段，越过末端即结束。 |
| Trace | 到第三段的最小成本为 6+min(4,1)=7；结束可来自第二或第三段。 |
Recall prompts
我的补充