状态机思维：从自动机到 DP 抽象

0. 元信息

• 主题路径：docs/topics/algo-design/subtopics/state-machine-thinking/README.md
• 父主题：algo-design
• 主分类：数据结构与算法
• 辅助分类：计算机基础
• 适合对象：掌握递归、DP 基础、BFS；想用更抽象的视角把问题转化为图问题的学习者
• 建议周期：1.5～2 周（每周 8～12 小时）
• 前置知识：recursion-and-backtracking、greedy-and-dp（部分题目）、Python collections.deque 与 BFS
• 最终目标：能把中等题抽象成有限状态机，画出状态转移图，选择 DP 或 BFS 实现，并解释为什么该范式最优

1. 学习路线

有限自动机（DFA / NFA）基础
  → 状态、事件、转移、接受态
  → 状态机 → DP：买卖股票 / 打家劫舍
  → 状态机 → BFS：单词接龙 / 拓扑序
  → 多维状态：网格、字符串、图上的 FSM
  → 隐式状态机：把"决策"作为状态
  → 状态压缩 DP（bitmask FSM）

每一步都画状态图。先画图，再写代码。

2. 阶段周数分配

每天 1.5～2 小时。1.5 周方案聚焦前 4 阶段；2 周方案多 2 天做状态压缩与综合题。

3. 九阶段表（精简）

3.1 核心知识

• FSM（Finite State Machine）：状态集合 + 事件 + 转移函数 + 接受态。
• DFA（确定）：每个状态对每个事件有唯一转移；NFA（非确定）：可以有多个转移。
• 状态机 → DP：状态就是 DP 维度；事件就是转移触发条件；权重就是转移代价。
• 状态机 → BFS：状态是节点；合法转移是边；求最短路径用 BFS / Dijkstra。
• 隐式状态：题目里没明说”状态”二字，但可以抽象为”做完某件事后所处的情形”。
• 多维状态：状态维度可以是 (下标, 选择, 资源)；如买卖股票第 i 天持有 / 未持有两个状态。
• 状态压缩：用 bitmask 表示集合；n ≤ 20 比较合适。

3.2 实践产出

• 5 道经典 FSM 入门（LeetCode 122 买卖股票 II、LeetCode 309 含冷冻期、LeetCode 188 买卖股票 IV、LeetCode 714 含手续费、LeetCode 213 打家劫舍 II）；
• 3 道 FSM + BFS（LeetCode 127 单词接龙、LeetCode 433 最小基因变化、LeetCode 752 打开转盘锁）；
• 3 道多维状态 FSM（LeetCode 487 最大连续 1 的个数 II、LeetCode 1186 删除一次得到子数组最大和、LeetCode 903 DI 序列的有效排列数）；
• 2 道状态压缩（LeetCode 526 优美的排列、LeetCode 847 访问所有节点的最短路径）。

3.3 可观察学会标准

• 不看答案在 20 分钟内写出买卖股票 II 的状态机 DP；
• 能把单词接龙抽象成 BFS 图问题；
• 能把”打开转盘锁”的状态空间画出来（4 位 × 10 种 = 10000 节点）；
• 能解释为什么 847 题用 dp[mask][i] 而不是 dp[mask]。

4. 第一周（每天 1.5~2 小时）

Day 1 约定：本计划使用 Python 3.10+。统一格式：python -X dev -W error -m py_compile foo.py；测试用 pytest；BFS 模板用 collections.deque。所有代码放进 algo-design/fsm/week<N>/ 目录；每个题目单独 .py 文件，配套 notes/<problem>.md 含状态转移图（节点 = 状态，边 = 事件）、复杂度推导、状态空间估算。

Day 7 执行次序

步骤 A —— 买卖股票 II 完整版（60~90 分钟）

1. 写二维 DP dp[i][hold]（i=天数，hold=0/1）；
2. 画状态转移图（两状态）；
3. 压一维 → 滚动变量；
4. 跑空 / 单天 / 全涨 / 全跌 4 类数据；
5. 对比 O(n) 空间与 O(1) 空间耗时。

步骤 B —— 4 类边界用例（30~45 分钟）

Day 7 当天必完成步骤 A；步骤 B 至少完成 B1、B4。

5. 阶段通用验收（精简）

1. 不看答案重写 10 道 FSM 题；
2. 用自己的话解释 FSM、DP、BFS 三者关系；
3. 画出每道题的状态转移图（节点 = 状态，边 = 事件 / 转移）；
4. 测试最小输入、最大输入、特殊情况（空、所有合法、全部非法）；
5. 至少准备 3 组自定义数据贴出实际输出；
6. 记录每题时间空间复杂度；
7. 能给现有 FSM 加新状态或新转移。

6. 最终验收

• 独立实现：5 道状态机 DP（122 / 309 / 188 / 213 / 714）、3 道状态机 BFS（127 / 433 / 752）、3 道多维状态（487 / 1186 / 903）、2 道状态压缩（526 / 847）；

• 至少完成 13 道题（LeetCode / CSES / AtCoder），分布建议：

  子阶段	题目数量	难度分布	平台建议
  状态机 DP 入门	5 道	2 Easy + 3 Medium	LeetCode 122 / 309 / 188 / 213 / 714
  状态机 BFS	3 道	1 Medium + 2 Hard	LeetCode 127 / 433 / 752
  多维状态 FSM	3 道	1 Medium + 2 Hard	LeetCode 487 / 1186 / 903
  状态压缩	2 道	1 Medium + 1 Hard	LeetCode 526 / 847

  约束：至少 5 道达到 Medium，至少 3 道达到 Hard；买卖股票 II 必须在 20 分钟内写出 O(1) 空间版本。

• 完成 1 个综合 Python 项目（自带 README，能被他人按文档复现）；

• 能用 15 分钟讲清 FSM 五元组、状态机 → DP 转化、状态机 → BFS 转化、n × 2^n 状态数估算、deadends 前置过滤的必要性。

7. 综合项目

首选：状态机算法可视化工具（必做：CLI 输入 + 输出 + 可选 GUI）。
备选：自动评测器（从 LeetCode 拉指定状态机题目的测试用例，本地批量跑、对比时间、生成错题本）。
备选：状态机题模板生成器（给定关键词「买卖股票 / 单词接龙 / 转盘锁」→ 输出 Python 模板）。

状态机算法可视化工具必做要求：

• 输入：stdin 接收题目名（stock_ii / stock_cooldown / word_ladder / open_lock / ugly_arrangement）+ 数据集（价格数组 / 单词列表 / deadends）；
• 输出：必输出（1）状态转移图（节点 + 边的文字描述）；（2）DP 转移表（每一步状态值）；（3）时间 / 空间复杂度 + 实际耗时；（4）BFS 步数（若适用）；
• 算法：必须用至少 2 种范式（状态机 DP + 状态机 BFS）；
• 进阶可选：matplotlib 画状态转移图 GUI、可对比”贪心 vs 状态机 DP”在 cooldown 题上的差异。

任何综合项目都必须包含：

1. 需求说明（含输入输出约定）；
2. 数据结构与算法选择理由（为何用状态机 DP、为何选这种状态维度）；
3. 核心模块说明（Solver / Recorder / Renderer 三层）；
4. 模块化源码（每题单独文件 + 公共 base class）；
5. 边界测试（空 / 单元素 / 全跌 / 全涨 + deadends 前置过滤）；
6. 运行说明（Makefile 或清晰的 python -m 命令）；
7. README（项目介绍、运行步骤、目录结构、复盘）；
8. notes/ 规范：

本主题贡献

3 职责

1. 把”当前处境”显式化为 FSM 五元组 (Q, Σ, δ, q0, F) —— Q 是状态集合（持有 / 未持有 / 冷却中 / 已用过 k 笔交易），Σ 是事件集合（价格数组中每天的 ±），δ 是转移函数（买 / 卖 / 持 / 冷），并区分 Moore 机（状态决定输出） 与 Mealy 机（转移决定输出）在买卖股票系题目上的等价转换。
2. 在 DP / BFS 两种实现路径间切换 —— 求最优解用状态机 DP（买卖股票 / 打家劫舍 / DI 序列），求最短转移步数用 BFS（单词接龙 / 最小基因变化 / 转盘锁）；用 guard clause 把 deadends 等非法前置状态在 BFS 入队前过滤（if next_state in deadends: continue），避免把死锁节点加入访问队列。
3. 用 Trie（前缀树 node[26] 子节点）把单词搜索问题接入 FSM、用 KMP（失败函数 next[] 数组）把”模式匹配”问题接入 FSM；状态压缩时用 bitmask 表示已访问集合（如 526 优美排列 mask & (1<<i)），估算 n × 2^n 状态数（如 n=15 时 491520）作为”该不该用状压”的判断阈值。

4 交付物

1. 13 道题解（5 状态机 DP + 3 BFS + 3 多维 + 2 状态压缩）+ 4 类边界用例日志（空 / 单天价格 / 全跌 / 全涨）。
2. 状态机可视化工具（CLI → 状态转移图节点/边表 + DP 转移表每步状态值 + BFS 步数 + deadends 前置过滤后的有效状态空间）。
3. 至少 5 道题的状态转移图（手画 + DOT 文件：买卖股票 II 的两状态 / 309 含冷冻期的三状态 / 打家劫舍 II 的环形拆两段 / 转盘锁的 10000 节点 / 526 优美排列的 bitmask）落 notes/state-diagrams/ + 至少 3 道 DP 题的状态转移表落 notes/dp-tables/。
4. BFS vs DP 范式对比文档 notes/bfs-vs-dp.md（单词接龙用 BFS 因求最短转移、股票 II 用 DP 因求最大累积收益 —— 同为 FSM 抽象，实现路径由”求最短”还是”求最值”决定）。

3 指标

1. 20 分钟内独立写出买卖股票 II 的状态机 DP（含 O(1) 空间滚动变量版本，覆盖持有 / 未持有两状态 + 买/卖/持三种转移）。
2. 把转盘锁的 4 位 × 10 种 = 10000 节点状态空间手画出来（含 deadends 前置过滤后的实际访问节点数估算，证明 BFS 状态空间不是”无限”）。
3. 在 n=15 时估算 bitmask 状态数 n × 2^n = 491520，主动放弃 bitmask 改用多维 DP 维度（说明状态数估算已成为”该不该用状压”的判断本能，而非盲目开 1<<n）。

许可证提示：CLRS 与 Sipser 自用学习合理引用；不要复制粘贴课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。CP-Algorithms 是 CC BY-SA。默认做法是读思路后自己重写代码，而不是复制 Editorial。

默认使用顺序：先读 Sipser 第 1 章建立 FSM 形式化心智 → 选读 CLRS 第 14、22 章（DP + BFS）→ 用 LeetCode 刷 8 道状态机题（按 tag）→ 用 labuladong / CP-Algorithms 对照 5 道卡住的题 → 实现买卖股票 II / 含 cooldown 完整推导 → 跑 VisuAlgo BFS 模拟器 → 选读 Halim 第 4 章 → 写复盘到 notes/retrospective.md。

8. 推荐开源资料

许可证提示：CLRS 与 Sipser 自用学习合理引用；不要复制粘贴课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。CP-Algorithms 是 CC BY-SA。默认做法是读思路后自己重写代码，而不是复制 Editorial。

默认使用顺序：先读 Sipser 第 1 章建立 FSM 形式化心智 → 选读 CLRS 第 14、22 章（DP + BFS）→ 用 LeetCode 刷 8 道状态机题（按 tag）→ 用 labuladong / CP-Algorithms 对照 5 道卡住的题 → 实现买卖股票 II / 含 cooldown 完整推导 → 跑 VisuAlgo BFS 模拟器 → 选读 Halim 第 4 章 → 写复盘到 notes/retrospective.md。

9. 学习资料汇聚（v0.3）

9.1 背景与动机

有限状态机的数学基础是 Kleene 在 1956 年提出的正则表达式与有限自动机等价定理。Mealy（1955）和 Moore（1956）分别提出 Mealy 机与 Moore 机，把”输出”作为转移的一部分。Rabin & Scott 在 1959 年因 NFA 与 DFA 等价证明获 Turing Award。在算法竞赛里，FSM 思维是 2010 年后逐渐成为中等难度题的常见抽象——把”当前处境”显式化能避开暴力枚举。

行业位置：FSM 是协议设计（TCP / TLS 状态机）、正则表达式（DFA 实现）、游戏 AI（敌人状态切换）、编译原理（词法分析）的核心。算法面试里”买卖股票”系列是 FSM DP 的代表。一句话总结：FSM 思维是把”我做完某件事后处在什么情形”显式化，再按情形做决策或搜索。

9.2 概念地图

flowchart LR
  State[状态]
  Event[事件]
  Transition[转移]
  Accept[接受态]
  DFA[DFA / NFA]
  FSMtoDP[FSM → DP]
  FSMtoBFS[FSM → BFS]
  Multidim[多维状态]
  Bitmask[状态压缩]
  Stock[买卖股票]
  WordLadder[单词接龙]
  Lock[转盘锁]
  TSP[TSP 状压]

  State --> Event
  Event --> Transition
  Transition --> Accept
  DFA --> FSMtoDP
  DFA --> FSMtoBFS
  FSMtoDP --> Multidim
  FSMtoDP --> Bitmask
  Stock --> FSMtoDP
  WordLadder --> FSMtoBFS
  Lock --> FSMtoBFS
  Bitmask --> TSP

核心关系：FSM 是底座抽象；DP / BFS 是两种实现路径；多维状态 + 状态压缩是 FSM 在算法竞赛里的扩展形态。

9.3 基础知识讲解

9.3.1 经典论文

9.3.2 经典书籍

9.3.3 优秀博客

9.3.4 核心人物

9.3.5 开发方法

9.4 经典问题与经典案例

9.5 学习难点

概念难点

思维难点

工程难点

9.6 技术标准与接口

9.6.1 Entity

9.6.2 Scope

• FSM 适用：协议状态、词法分析、博弈状态、决策序列、网格 / 字符串上的转移。
• 不适用：纯组合数学（用组合公式）、最短路（图算法）。
• 与 DP / BFS 关系：FSM 是抽象；DP / BFS 是实现路径。

9.6.3 Structure

• FSM 五元组：(Q, Σ, δ, q0, F) —— 状态集、字母表、转移函数、初始状态、接受态。
• DP 视角：状态 = DP 维度；转移 = DP 方程；初始化 = base case。
• BFS 视角：状态 = 节点；边 = 合法转移；距离 = BFS 步数。

9.6.4 Ecosystem

• 工具：collections.deque（BFS）、functools.lru_cache（DP memo）、re（正则 DFA）。
• 在线评测：LeetCode、AtCoder、Codeforces。
• 训练集：LeetCode 状态机专题、CSES Graph 章节。

9.6.5 Depth Tiers

本子主题目标：L3。能画状态转移图 + 选择正确实现路径 + 解释空间复杂度即达到。

9.6.6 Source

• CLRS 官网：第 4 版第 14 章 DP。
• Sipser《Theory of Computation》：第 1 章 FSM 形式化。
• CP-Algorithms：BFS / DP 章节。
• 引用版本快照日期：2026-07-30。

10. 常见误区

• 把状态与决策混为一谈；
• 状态维度过细，导致状态空间爆炸；
• BFS 时忘了 visited，死循环或超时；
• 转盘锁题忘了过滤 deadends；
• 买卖股票 II 写成”贪心”——贪心在 cooldown 版会出错；
• 状压 DP 算错状态数（2^25 = 33554432，n=20 已是 104 万）；
• 单词接龙用 DFS 而非 BFS，最短路径算错；
• bitmask 操作混淆 1<<i 与 i；
• 多维状态 DP 写出 N 重循环，自己都数不清维度；
• 状态机 DP 写成贪心，遇到边界条件就崩；
• 写完不复盘，下周遇到同类型还是不会。

11. 所有知识点分类

1. 编程语言（辅）：Python collections.deque 做 BFS、functools.lru_cache 做 FSM DP memo、位运算 (1<<i、mask | (1<<i)、mask & ~(1<<i))、set 做 BFS visited、re 模块（DFA 实现正则）。
2. 数据结构与算法（主）：FSM 五元组（Q, Σ, δ, q0, F）、DFA / NFA、Mealy / Moore 机、状态机 → DP（买卖股票 / 打家劫舍）、状态机 → BFS（单词接龙 / 转盘锁）、多维状态、状态压缩（bitmask FSM）。
3. 计算机基础：正则表达式与有限自动机等价、词法分析（正则 → NFA → DFA 子集构造）、协议状态机（TCP / TLS）、NFA → DFA 转换的子集构造法。
4. 工程技术：画状态转移图（节点 = 状态，边 = 事件）、估算 n × 2^n 状态数选 DP 或 BFS、双向 BFS 缩小搜索空间、deadends 等非法状态前置过滤。
5. Web 与后端：HTTP 协议状态机、TCP 连接状态、正则路由匹配（DFA）；本计划不展开。
6. 前端与客户端：浏览器事件循环的状态视角、表单状态机；本计划不展开。
7. 数据与人工智能：HMM / CRF 序列标注本质是 FSM；本计划不展开。
8. 项目与职业能力：LeetCode 122 / 127 / 188 / 213 / 309 / 433 / 487 / 752 / 903 等 FSM 高频面试题、20 分钟写出买卖股票 II 状态机 DP、估算状态空间选择 DP 或 BFS。

本计划归属：数据结构与算法 主 + 编程语言 辅。