有限状态机 DP

数学 / 逻辑形态

dp[i][s] 表示处理到时刻 i 且处于模式 s 的最优值。转移 dp[i][s']=Agg_s(dp[i-1][s]+cost(s→s',i))，仅允许状态图中的边。

识别信号

每个时刻只能处于少量互斥模式。
动作会改变持有/空闲/冷却/阶段等资格。
未来只需知道当前模式而非完整历史。
限制可用有限计数或阶段编码。
自然语言规则可画成小状态图。

容易误判的相似信号

Signal	Why it is different
状态数量随 n 指数增长	这不是有限状态机，应考虑 bitmask、区间或其他结构。
无历史依赖的局部收益	若每步独立，直接聚合即可，不需要 DP。
可证明永不后悔的动作	若单一贪心规则成立，状态机 DP 是过度建模。

核心不变量

处理完时刻 i 后，每个状态值是所有以该模式结束的合法历史中的最优值；非法历史永不进入有限状态。

状态、转移与处理顺序

Item	Definition
State	时刻 i 与有限模式 s；不可达模式初始化为 -inf/inf。
Transition	对状态图每条合法边，用上一时刻源状态加本次动作贡献更新目标状态。
Frontier / order	时间从前到后；每轮从 old 向 new 转移，防止同一时刻连走多条边。

Python 骨架

def max_gain(prices):
    # States: flat or holding one unit; any number of transactions.
    flat, hold = 0, float('-inf')
    for price in prices:
        old_flat, old_hold = flat, hold
        flat = max(old_flat, old_hold + price)
        hold = max(old_hold, old_flat - price)
    return flat

正确性思路

初始 flat=0 且 hold 不可达，准确描述处理零时刻。
任一以目标状态结束的历史，最后动作对应状态图某条入边；转移枚举全部入边。
源状态按归纳已最优，聚合后目标状态也最优；最终在允许终态中取答案。

复杂度

Time	Space	Parameters
O(n·\|E_s\|)，固定状态图时 O(n)	O(\|S\|)	n 为时刻数，S/E_s 为模式与合法转移。

边界条件

空时间线
初始可达状态
必须在特定终态结束
同日动作是否允许连续
交易/阶段计数维度
负无穷参与算术

错误模式

Pattern	Why it fails / fix
原地更新混入本轮新值	若规则不允许同刻连动，应从 old 快照统一生成 new。
状态不互斥或不充分	同一历史落入多个状态会重复计数；未来依赖未编码会错误合并。
非法状态初始化为 0	会凭空产生收益；不可达最优态应为 -inf。
只画状态不标动作	边上的条件与收益才定义转移，不能凭名称猜。

选择与排除规则

先列互斥且未来充分的模式。
画合法转移边并标动作收益。
用 old/new 区分时间层。
明确允许的起始与终止状态。

Relation	Template	Boundary
generalization	线性 DP / 一维状态递推	每个位置还存在多个互斥模式。
analogy	树形 DP	树节点拥有互斥模式，边定义兼容转移。

原创微型例子

环节	内容
Result	最终空仓收益 3，对应 1 买 4 卖。
Setup	价格 [3,1,4]，每次最多持有一件。
Trace	到价格 1 时 hold=max(-3,-1)=-1；价格 4 时 flat=max(0,-1+4)=3。

Recall prompts

什么叫状态对未来充分？
为什么 old/new 快照能防止同刻多动作？
不可达状态为何不能初始化为 0？

数学 / 逻辑形态

识别信号

容易误判的相似信号

核心不变量

状态、转移与处理顺序

Python 骨架

正确性思路

复杂度

边界条件

错误模式

选择与排除规则

相关模板

原创微型例子

Recall prompts

我的补充