第5章 · 状态间的奇妙转移——动态规划

按图解版第5章重建从搜索到动态规划、仓储转移、股票状态、猫舍bitmask、运输与会议剪枝、路径规划、矩阵链和文本处理。

学习目标

  • 能解释初探动态规划与拼图游戏——从搜索到动态规划在“第5章 · 状态间的奇妙转移——动态规划”中的适用条件
  • 能围绕“怎样由最优子结构、状态定义、转移依赖和计算顺序构造动态规划？”运行正常与失败轨迹，定位第一处错误决策
  • 能用“第5章 · 状态间的奇妙转移——动态规划的题面摘要、约束表、输入生成器、算法伪码或代码版本、复杂度推导、正确性理由、最小反例、实际输出与资源统计。”证明“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”

来源、目录与技术核对边界

“第5章 · 状态间的奇妙转移——动态规划”以天瓏书店详细书目与目录核对段忠杰、顾业鸣著、中国水利水电出版社、ISBN 9787522615059、245 页以及全书 6 章；该页标出版日期 2023 年 6 月 1 日。河南省政府采购书目记录同一 ISBN、题名、作者和出版社，但出版时间写作 2023 年 5 月。日期口径相差一个月，本课程保留差异，不自行断言哪一天是正式首发日。

对“第5章 · 状态间的奇妙转移——动态规划”而言，公开来源只提供书目和详细目录，不含可授权改写的完整正文；本站的解释、推导、代码、交互、练习和答案均为独立教学重写。目录页第 4 章和第 6 章标题存在明显 OCR 或排版异常，站内按上下文规范化标题，但在清单中披露校正。

“第5章 · 状态间的奇妙转移——动态规划”的技术事实另以Bellman 动态规划原始论文复核：技术来源 1。来源用于检查概念、语言语义或历史算法边界，不把现代竞赛规则静默投射成 2023 年原书的逐字内容。

围绕“怎样由最优子结构、状态定义、转移依赖和计算顺序构造动态规划？”，先预测正确轨迹，再只注入“状态省略了影响未来决策的信息，使两个不同子问题被错误合并”。若不能用最小反例定位第一处错误决策，就拒绝当前算法解释。

从“递归已经正确，为什么还超时”开始

先预测：两个递归调用参数相同，却来自不同历史路径，它们是否需要各算一次？如果从该点开始的合法动作与最优答案只由参数决定，那么历史已经被参数充分概括；重复展开只是浪费。

不是“填二维表”，而是把搜索树中未来相同的节点合并为状态图。

5.1 初探动态规划

一个DP设计必须完整回答：

  1. 状态表示了哪个子问题；
  2. 每个动作怎样产生后继；
  3. 当前答案怎样由后继答案组合；
  4. base case是什么；
  5. 状态按什么顺序求值；
  6. 最终答案位于哪个状态。

5.1.1 拼图游戏——从搜索到动态规划

拼图游戏——从搜索到动态规划的关键是识别重复状态。若一个关卡位置由(row,col,remaining_moves)完整决定，那么不同路径到达同一三元组后，未来可行解集合相同，可以缓存。

设状态集合为SS，每状态最多bb个动作。树搜索可能展开O(bd)O(b^d)个路径节点；记忆化后，每个可达状态只求一次：

T=O(∣S∣⋅b)T=O\left(|S|\cdot b\right)

这不是免费降复杂度。若状态中必须保留整个棋盘，∣S∣|S|仍可能指数大；DP消除的是重复路径，不会消除本质上不同的状态。

5.1.2 物流仓库——状态的转移

物流仓库——状态的转移可把第dd天开始时库存xx写为dp[d][x]。订货量qq满足容量与需求约束，下一库存为：

x′=x+q−demand⁡[d]x'=x+q-\operatorname{demand}[d]

可写为：

dp[d][x]=min⁡q{orderCost⁡(q)+holdCost⁡(x′)+dp[d+1][x′]}dp[d][x]=\min_q\left\{\operatorname{orderCost}(q)+\operatorname{holdCost}(x')+dp[d+1][x']\right\}

若允许缺货但有罚金，负库存也许合法；若不允许，负x′x'必须剪掉。业务contract改变状态域，而不只是改一个常数。

5.2 状态的巧妙定义

状态的巧妙定义遵循一个张力：字段太少会错误合并未来不同的历史；字段太多会让状态空间爆炸。判断方法是提出反例：能否找到两个编码相同的历史，下一步合法动作或最优后缀却不同？

5.2.1 股票投资计划——不同的状态和转移

股票投资计划——不同的状态和转移说明“天数”不够。第dd天结束时，持有股票与不持有股票的未来不同：

cashd=max⁡(cashd−1,holdd−1+pd),holdd=max⁡(holdd−1,cashd−1−pd)\begin{aligned} cash_d&=\max(cash_{d-1},hold_{d-1}+p_d),\\ hold_d&=\max(hold_{d-1},cash_{d-1}-p_d) \end{aligned}

若同一天计算cash后立即用新cash更新hold，就可能在同一价格完成不符合题意的多次动作。应从旧状态同时转移到新状态。加入交易费、冷冻期、最多kk次交易时，还需扩展状态字段。

long long cash = 0;
long long hold = -price[0];
for (std::size_t day = 1; day < price.size(); ++day) {
    const long long next_cash = std::max(cash, hold + price[day]);
    const long long next_hold = std::max(hold, cash - price[day]);
    cash = next_cash;
    hold = next_hold;
}

5.2.2 流浪猫的家——状态压缩与状态剪枝

流浪猫的家——状态压缩与状态剪枝可把“哪些猫已经分配”编码为bitmask。令第ii位表示猫ii是否已有住处：

mask′=mask∣(1≪i)mask'=mask\mathbin{\vert}(1\ll i) 
for (int mask = 0; mask < (1 << cat_count); ++mask) {
    const int shelter = std::popcount(static_cast<unsigned>(mask));
    for (int cat = 0; cat < cat_count; ++cat) {
        if ((mask & (1 << cat)) == 0 && allowed[cat][shelter]) {
            dp[mask | (1 << cat)] += dp[mask];
        }
    }
}

若每个shelter恰放一只猫，已分配数量可由popcount(mask)恢复，无需再存shelter index。若容量不同或允许空位，这个推导失效，必须增加状态。

5.3 转移方式的神奇优化

转移方式的神奇优化有两条路线：减少状态，或减少每状态要检查的决策。任何剪枝都要给出dominance、单调性或上下界证明。

5.3.1 运输计划——在转移中剪枝

运输计划——在转移中剪枝可维护Pareto frontier。若状态A装载不少于B、成本不高于B，而且未来只关心“剩余容量与总成本”，B被A支配，永远不可能进入更优完整方案。

需要谨慎确认未来转移对两个状态同样可用。若A较重会限制未来路线、货物类别不同影响兼容性，单看load与cost不足以判定支配。

5.3.2 会议安排——在决策中剪枝

会议安排——在决策中剪枝考虑带价值且不能重叠的会议。按结束时间排序，令p(i)p(i)为与会议ii兼容的最后一个会议下标：

dp[i]=max⁡(dp[i−1], valuei+dp[p(i)])dp[i]=\max\left(dp[i-1],\ value_i+dp[p(i)]\right)

两个决策足够：不选ii，答案是前i−1i-1个会议最优值；选ii，与它冲突的区间都被一次跳过，只接到p(i)p(i)。二分查找p(i)p(i)后，总成本O(nlog⁡n)O(n\log n)。

5.4 经典的动态规划算法

经典的动态规划算法不是题型清单，而是几类状态图：序列前缀、网格DAG、subset lattice和区间分割。它们都依赖。识别依赖图比记住数组形状更可靠。

5.4.1 路径规划——用动态规划创造算法

路径规划——用动态规划创造算法以只能向右或向下的网格为例。每格是状态，前驱只有上方与左方：

dp[r][c]=w[r][c]+min⁡(dp[r−1][c],dp[r][c−1])dp[r][c]=w[r][c]+\min(dp[r-1][c],dp[r][c-1]) 
for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
        if (r == 0 && c == 0) continue;
        long long best = INF;
        if (r > 0) best = std::min(best, dp[r - 1][c]);
        if (c > 0) best = std::min(best, dp[r][c - 1]);
        dp[r][c] = weight[r][c] + best;
    }
}

因为边只指向行列更大的格子，行优先顺序是拓扑序。若允许上下左右移动，状态图可能有环，应使用Dijkstra等通用最短路，不能照抄一次填表。

5.4.2 矩阵乘积——用动态规划优化算法

矩阵乘积——用动态规划优化算法不改变矩阵顺序，只选择括号。矩阵AiA_i尺寸为pi−1×pip_{i-1}\times p_i，令dp[l][r]为相乘区间$l..r`最少标量乘法：

dp[l][r]=min⁡l≤k<r(dp[l][k]+dp[k+1][r]+pl−1pkpr)dp[l][r]=\min_{l\le k\lt r}\left(dp[l][k]+dp[k+1][r]+p_{l-1}p_kp_r\right)

区间长度从2递增，保证较短子区间已求出。需要重建括号时，另存达到最小值的splitkk；只存成本会丢失方案。

5.5 玩转自然语言——动态规划在文本处理中的应用

玩转自然语言——动态规划在文本处理中的应用常以两个前缀为状态。编辑距离令dp[i][j]表示把源前ii个字符变为目标前jj个字符的最少操作：

dp[i][j]=min⁡{dp[i−1][j]+1deletedp[i][j−1]+1insertdp[i−1][j−1]+[ai≠bj]match or replacedp[i][j]=\min \begin{cases} dp[i-1][j]+1 & \text{delete}\\ dp[i][j-1]+1 & \text{insert}\\ dp[i-1][j-1]+[a_i\ne b_j] & \text{match or replace} \end{cases} 
for (std::size_t i = 1; i <= a.size(); ++i) {
    for (std::size_t j = 1; j <= b.size(); ++j) {
        int replace = dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]);
        dp[i][j] = std::min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, replace});
    }
}

同一框架可扩展到词切分、序列标注、语音解码与字符串对齐。若局部操作成本来自模型概率，通常把概率乘积取负对数转为路径成本，再在状态图上求最短路。

正式节点与算法证据

  • ：第 1 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 2 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 3 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 4 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 5 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 6 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 7 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 8 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 9 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 10 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 11 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 12 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。
  • ：第 13 个正式节点要能回到“每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。”，并给出成功输入与失败反例。

约束到算法决策

先固定问题，再比较策略

怎样由最优子结构、状态定义、转移依赖和计算顺序构造动态规划？

问题前提

写出初探动态规划的输入域、输出合同、规模和数值范围。

算法决策

只比较能够完整覆盖拼图游戏——从搜索到动态规划前提的候选策略。

验收证据

保存第5章 · 状态间的奇妙转移——动态规划的最小、边界与对抗输入。

正式节点：初探动态规划、拼图游戏——从搜索到动态规划、物流仓库——状态的转移、状态的巧妙定义、股票投资计划——不同的状态和转移、流浪猫的家——状态压缩与状态剪枝、转移方式的神奇优化、运输计划——在转移中剪枝、会议安排——在决策中剪枝、经典的动态规划算法、路径规划——用动态规划创造算法、矩阵乘积——用动态规划优化算法、动态规划在文本处理中的应用

执行轨迹

用同一输入比较正常与失败路径

  1. 01形式化初探动态规划的输入与输出
  2. 02选择拼图游戏——从搜索到动态规划并声明不变量
  3. 03执行物流仓库——状态的转移并记录成本
  4. 04用动态规划在文本处理中的应用核对正确性、终止和资源

必须保持：每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。

反例与证据包

让错误策略在最小输入上失败

当前基线满足：每个状态具有唯一语义，转移只读取已建立子问题并覆盖所有合法决策。

小结

本章从拼图游戏的搜索到动态规划，借物流仓库理解状态的转移；股票投资计划展示不同的状态和转移，流浪猫的家展示状态压缩与状态剪枝。运输计划和会议安排分别说明在转移中剪枝与在决策中剪枝。

路径规划展示用动态规划创造算法，矩阵乘积展示用动态规划优化算法，文本处理则把前缀对齐推广到自然语言。DP的核心始终是充分状态、完备转移、正确base case和依赖顺序。

练习与答案

练习

  1. 问题 1：建立算法合同。 回答“怎样由最优子结构、状态定义、转移依赖和计算顺序构造动态规划？”，并写出约束、决策、不变量和验收结果。
  1. 问题 2：构造最小反例。 只采用“状态省略了影响未来决策的信息，使两个不同子问题被错误合并”，怎样确认失败来自算法而不是实现噪声？
  1. 问题 3：覆盖正式节点。 用一个证据包串联初探动态规划、拼图游戏——从搜索到动态规划、物流仓库——状态的转移、状态的巧妙定义、股票投资计划——不同的状态和转移、流浪猫的家——状态压缩与状态剪枝、转移方式的神奇优化、运输计划——在转移中剪枝、会议安排——在决策中剪枝、经典的动态规划算法、路径规划——用动态规划创造算法、矩阵乘积——用动态规划优化算法、动态规划在文本处理中的应用，并解释为什么复杂度更低不必然在给定规模上更快。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

初探动态规划

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

拼图游戏——从搜索到动态规划

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

物流仓库——状态的转移

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

状态的巧妙定义

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

股票投资计划——不同的状态和转移

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

流浪猫的家——状态压缩与状态剪枝

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

转移方式的神奇优化

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

运输计划——在转移中剪枝

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

会议安排——在决策中剪枝

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

经典的动态规划算法

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

路径规划——用动态规划创造算法

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

矩阵乘积——用动态规划优化算法

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

动态规划在文本处理中的应用

“第5章 · 状态间的奇妙转移——动态规划”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

资料与写作方式声明

本章以《深入浅出算法竞赛（图解版）》的权威目录界定学习范围，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…