动态规划 = 全局最优的逆向求解
解决什么问题：如何把一个复杂的多步决策问题分解为简单的子问题—— 不是逐步求解，而是从终点倒推，找到全局最优。
业务问题
真实场景
场景 1：最短路径算法
业务：导航系统的最短路径
问题：
- 从 A 到 B 有 N 条路径
- 直接尝试所有路径太慢
- 需要高效的算法
动态规划解法：
- 从终点 B 倒推
- 每个节点到 B 的最短距离 = 子问题
- 子问题解 = 全局最优场景 2：资源分配
业务：有限的资源如何分配
问题：
- 总资源 R = 1000
- N 个项目，每个需要不同资源
- 最大化总收益
动态规划解法：
- 状态 = 已分配的资源
- 决策 = 给哪个项目分配多少
- 从少资源到多资源逐步求解场景 3：编辑距离
业务：两个文本的相似度
问题：
- 字符串 A 转字符串 B 的最少操作
- 操作 = 增 / 删 / 改
动态规划解法：
- 子问题 = A[i:] 转 B[j:] 的最少操作
- 从末尾倒推
- 得到全局最优失败的典型做法
做法 1：贪心算法
✗ 每步都选当前最优
✗ 不考虑全局
后果：局部最优 ≠ 全局最优做法 2：穷举
✗ 尝试所有可能
✗ 时间复杂度爆炸
后果：不可行做法 3：递推（无记忆）
✗ 直接递推
✗ 重复计算子问题
后果：效率低控制论视角
数学原型
钱学森《工程控制论》Ch 9 §9 引言：
"动态规划是求解多步决策问题的有力工具——它把原问题分解为重叠的子问题，通过逆向求解（从终点倒推），利用最优性原理，得到全局最优解。"
控制论解法
动态规划的核心：
状态：描述系统在某一时刻的特征
决策：从一个状态到另一个状态的选择
转移：决策带来的状态变化
代价：决策的代价 / 收益
最优性原理：
- 整体最优 ⟺ 局部最优
- 子问题的最优 = 全局最优的一部分
逆向求解：
- 从终点开始
- 每个状态的最优值 = 子问题最优值 + 当前决策
- 逐步倒推与业务的对应
| 控制论概念 | 软件工程 |
|---|---|
| 多步决策 | 多阶段决策 |
| 状态 | 系统的中间状态 |
| 决策 | 每个阶段的选择 |
| 代价 | 收益 / 成本 |
| 最优性原理 | 子问题独立 |
| 逆向求解 | 倒序计算 |
核心概念
定义
动态规划：把复杂的多步决策问题分解为重叠的子问题，通过最优性原理和逆向求解，得到全局最优解。
软件工程对位：复杂决策问题的分解与求解。
动态规划的四个要素
1. 状态：
- 描述系统在某一时刻的特征
- 例：剩余资源、当前位置、已分配量
2. 决策：
- 从一个状态到另一个状态的选择
- 例：分配多少资源、走哪条路径
3. 转移：
- 决策带来的状态变化
- 例：分配后剩余资源 = 总 - 已分配
4. 代价 / 收益：
- 决策的代价 / 收益
- 例：分配资源的收益、走路径的距离关键属性
| 属性 | 含义 |
|---|---|
| 最优子结构 | 整体最优 = 子问题最优 + 当前决策 |
| 重叠子问题 | 子问题被多次使用 |
| 状态转移 | 状态之间的转换规则 |
| 逆向求解 | 从终点倒推 |
| 记忆化 | 缓存子问题结果 |
动态规划 vs 贪心 vs 穷举
| 方法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 动态规划 | 多项式 | 有最优子结构 |
| 贪心 | 多项式 | 局部最优 = 全局最优 |
| 穷举 | 指数 | 规模小 |
| 递归 | 指数 | 无重叠子问题 |
工程实践
步骤 1：识别问题是否适合动态规划
判断标准：
1. 有最优子结构？
- 整体最优 = 子问题最优 + 当前决策
- 例：最短路径、编辑距离
2. 有重叠子问题？
- 同样的子问题被多次求解
- 例：Dijkstra、Knapsack
3. 状态可枚举？
- 状态空间有限
- 可以存储所有状态
→ 都满足 = 适合动态规划步骤 2：定义状态
状态定义：
- 状态的维度（如位置、资源、时间）
- 状态的取值范围
- 状态的存储方式
例（最短路径）：
- 状态 = (当前位置, 已走路程)
- 状态空间 = N × 最大距离
- 存储 = 二维数组
例（资源分配）：
- 状态 = (当前项目, 已分配资源)
- 状态空间 = N × R
- 存储 = 二维数组步骤 3：定义决策和转移
决策和转移：
- 决策空间 = 所有可能的选择
- 状态转移 = (当前状态, 决策) → 下一状态
例（最短路径）：
- 决策 = 选择下一步的城市
- 转移 = (当前位置, 决策) → (下一位置, 路程+边权重)
例（资源分配）：
- 决策 = 给当前项目分配多少资源
- 转移 = (项目索引, 已分配) → (项目索引+1, 已分配+分配量)步骤 4：逆向求解
逆向求解步骤：
1. 初始化：
- 终点状态 = 已知最优值（通常是 0）
- 其他状态 = 未知
2. 状态转移：
- 对每个状态，计算最优决策
- V(状态) = min/max (代价(决策) + V(下一状态))
3. 倒推：
- 从已知状态推未知状态
- 直到所有状态都有值
4. 路径回溯：
- 从起点出发
- 根据 V 选择最优决策步骤 5：实现 + 优化
实现：
1. 简单递归 + 记忆化
2. 自底向上 DP 表
3. 空间优化（滚动数组）
优化：
- 时间复杂度：从 O(2^n) 降到 O(n^2)
- 空间复杂度：从 O(n^2) 降到 O(n)常见反模式
反模式 1：贪心但不适合
症状：
- 用贪心算法
- 但局部最优 ≠ 全局最优
后果：错误结果
正解：用动态规划反模式 2：状态定义错误
症状：
- 状态不够精细
- 遗漏关键信息
后果：算法错误
正解：仔细设计状态反模式 3：复杂度爆炸
症状：
- 状态空间太大
- 时间 / 空间复杂度爆炸
后果：不可行
正解：状态压缩 / 剪枝工程实例
实例 1：调度优化
业务：N 个任务，单机调度，最大化收益
状态：
- dp[i][t] = 处理完前 i 个任务、耗时 t 的最大收益
转移：
- 不做任务 i：dp[i][t] = dp[i-1][t]
- 做任务 i：dp[i][t] = dp[i-1][t-time[i]] + profit[i]
求解：
- 从 dp[0][0] = 0 开始
- 逐步递推
- 得到最优解
应用：
- 任务调度
- 资源分配
- 投资组合实例 2：库存管理
业务：库存的最优补货策略
状态：
- 当前库存 = s
- 未来需求 = d
转移：
- 补货量 = u
- 下一期库存 = s + u - d
代价：
- 库存成本 + 缺货成本 + 补货成本
动态规划：
- 找到最优补货策略
- 最小化总成本实例 3：A/B 实验的多步决策
业务：分阶段推出新功能
状态：
- 当前阶段 = s（阶段 1, 2, 3）
- 当前用户覆盖 = c
转移：
- 扩大覆盖 = c + Δ
- 维持覆盖 = c
代价：
- 收益：覆盖增加带来的业务价值
- 风险：覆盖增加带来的故障成本
动态规划：
- 找到最优推出节奏
- 最大化收益 / 风险比性能指标
动态规划健康指标
| 指标 | 设计目标 | 衡量方法 |
|---|---|---|
| 算法正确性 | 100% | 已知答案对比 |
| 时间复杂度 | 多项式 | 计算时间 |
| 空间复杂度 | 合理 | 内存使用 |
| 最优解偏差 | 0 | 与理论最优对比 |
监控设计
关键监控：
- 算法执行时间
- 内存使用
- 解的质量（与历史对比）
告警分级：
- P2：执行时间 > 设计目标 50%
- P1：执行时间 > 设计目标 100%
- P0：算法错误 / 解质量差边界判断
何时不用
场景 1：无最优子结构
- 整体最优 ≠ 子问题最优 + 当前决策
- 不适合动态规划
→ 用其他方法场景 2：状态空间太大
- 状态数过多
- 时间 / 空间爆炸
→ 用近似算法场景 3：贪心足够
- 局部最优 = 全局最优
- 动态规划过度设计
→ 用贪心与其他方法论的边界
| 相邻概念 | 区别 |
|---|---|
| 自寻最优点 | 自寻最优点关注"无模型搜索"；本方法论关注"已知模型的最优" |
| 极大值原理 | 极大值原理关注"连续最优控制"；本方法论关注"离散多步决策" |
| 递归 | 递归无记忆化；动态规划有记忆化 |
何时升级（更复杂的优化）
当以下情况出现时，考虑升级：
1. 状态空间太大 → 状态压缩
2. 多目标优化 → 多目标 DP
3. 不确定性 → 随机 DP
4. 大规模问题 → 分布式 DP关键洞察
钱学森 Ch 9：动态规划是求解多步决策问题的核心方法。
软件工程的优化智慧：
不是所有问题都需要全局搜索——很多问题可以通过动态规划分而治之。
应用场景：
- 路径规划 → Dijkstra、Floyd
- 资源分配 → 背包问题变种
- 文本相似度 → 编辑距离
- 生物信息 → 序列比对
- 金融工程 → 期权定价
好的动态规划 = 正确的状态 + 正确的转移 + 正确的优化
相关链接
IDDD 对位
- 动态规划 = 阶段性决策 → 用例编排（Ch 14）
- 最优路径 = Saga → 应用服务 vs 领域服务（Ch 14）：Saga 编排
- 状态压缩 = 聚合 → 聚合 4 规则（Ch 10）
核心：动态规划 = 跨阶段最优决策——IDDD Saga 编排和 cybernetics DP 同构。