动态规划经典模型：从状态、决策到三类 DP 模型
动态规划经典模型：从状态、决策到三类 DP 模型 动态规划经常被讲成一堆题型：背包、区间 DP、树形 DP、数位 DP、插头 DP、最短路、状态压缩……但如果只记题型，很容易出现一个问题：看到新题时，不知道它到底应该归到哪一类，也不知道状态为什么要这么设计。 更好的理解方式是：动态规划不是先背转移方程，而是先把问题拆成一系列具有相同后效性的子问题。只要能把大量具体决策前缀合并成有限个“状态”，并且这些状态对后续决策的影响相同，就可以用动态规划来减少枚举量。 本文按 slide 的思路，把动态规划整理成三个经典模型： 固定多阶段决策类动态规划； 路径规划类动态规划； 扩展边界类动态规划。 这三类模型并不是互斥的“标签”，而是三种理解 DP 的视角。它们分别回答了三个问题：阶段怎么推进、路径怎么延伸、边界怎么扩张。 1. 动态规划到底在做什么 动态规划常用于组合优化问题和计数问题。它的核心思想是： 将原问题拆成若干子问题，并且每个子问题都能用几个更简单子问题的解快速得到。 这句话和分治、递推、递归很像，但动态规划的关键不只是“拆”，而是合并重复的子问题。 一个暴力搜索会枚举很多具体的决策过程，例如： 第一步怎么选； 第二步怎么选； 第三步怎么选； 当前已经形成了什么局面； 后面还能怎么走。 动态规划做的是：如果若干个决策前缀对后续的影响完全一样，就把它们归并到同一个状态里。之后不再关心它们具体是怎么来的，只关心这个状态对应的最优值、方案数或可行性。 所以，DP 的本质可以简化为四件事： 定义阶段：问题推进到哪里了； 定义状态：当前需要保留什么信息，才能决定后面怎么做； 设计决策：从当前状态可以做哪些选择； 合并影响：把后效性相同的决策前缀合并起来。 2. 固定多阶段决策类动态规划 第一类是最直观的动态规划：固定多阶段决策类 DP。 这类问题有明确的阶段特征。每个阶段都要做一次或若干次决策，当前阶段的状态和当前决策共同决定下一阶段会进入什么状态。 可以抽象成下面这个过程： 阶段 i 的状态 + 当前阶段的决策 -> 阶段 i + 1 的状态 这种模型的核心是： 每种前 i 个阶段的有效决策前缀，都被包含在阶段 i 的某个状态中； 同一个状态中的所有决策前缀，对后续决策的影响相同； 因此可以从“枚举每一种决策前缀”变成“枚举每一种状态和下一步决策”。 这类 DP 的典型例子包括组合数计算、0/1 背包、数位 DP 等。 3. 例一：组合数计算 问题是：有 n 个可区分的球，现在要从中拿出 m 个，问一共有多少种拿法。 ...