DP 1 | 小明の雜貨屋

本文是个人对算法竞赛中一些 DP（动态规划）题目的经验总结。

文章偏向经验分享和归纳总结，而非教程，适合有一定 DP 基础的同学进阶。我尽量把思考过程写得详细些。

笔者在队内对 DP 的主要贡献是发现 DP 然后喂给队友，检查做法的合法性，有时候也会参与优化 DP。所以写过的 DP 经典题并不多，文章里的例子大多是 24, 25 年区域赛题。

文章的目录是按自己的理解设计的，可能与传统的 DP 教学大纲有些出入，具体理由写在各章节里。

（不保证表述绝对严谨。

DP 概述

基本概念与分类

一般认为，DP（Dynamic Programming，动态规划）是一种将原问题分解为简单子问题求解复杂问题的方法。广义上说，递推也可以算作 DP 的一种。

从定义就能看出，DP 最重要的是 子问题 （即状态）。我们将一个复杂的问题拆解为若干个（在时空都允许范围内的）子问题，存储若干信息，再利用子问题拼凑出所需问题的解。

DP 问题按其功能大致有三类：最优化 、计数和判定。判定类 DP 可视为计数 DP 的一种，即方案数存 bool；也可视为最优化的一种，即对可行性取 max。所以下文我们只讨论 最优化 和计数两类 DP。

DP 的本质结构

DP 本质是一个具有 自动机 功能的 有向无环图 结构：

从 起始状态（源点，已知信息） 开始，
逐个向自动机中输入字符，并 按转移方程转移（走有向边），到达某个 节点（状态，子问题），接着有走有向边到达另一个节点，如此重复，
最终达到 接受状态（汇点，所求答案的一部分）。

DP 有一些必要的条件，放在有向无环图中的表述就是：

最优子结构——一个问题的最优解包含其子问题的最优解。一个问题可以理解为从源点到当前节点所有路径，想到达当前节点，必然需要经过一个入点，这个入点所代表的问题就是子问题，转移方程保证了我们可以通过父节点的最优值来构造子节点的最优值。
子问题重叠——这是一张图，而不是树，存在资源复用。最简单的例子是斐波那契数列的暴力递归（树） vs. 记忆化搜索（图）。
无后效性——图中无环 / 存在拓扑序。想要求得某个点的信息，必须保证它所需的信息与自己无关。
（对于计数 DP）计数不重不漏——接受状态集合必须恰好是所求答案的分拆，不能存在某个情况在两个接受状态中出现。

上述几个特征只能用于检验 DP 的合法性，在此之前，设一个合理的状态（子问题）是最重要的。

何时用 DP？DP vs. 其它相关问题

DP vs. 贪心

（个人认为）贪心是 DP 的一个特例。

DP 在做决策时（选择哪条入边），会考虑所有可能的父节点，会保留所有入边的可能性，取其中的最优值。
贪心在做决策时，是短视的，它只选择当前看起来最优的入边，而不考虑这个选择是否对未来最优。

如果 DP 决策的 局部最优就是全局最优，那么可以考虑用贪心解决。还有些问题能直接 $\mathcal{O}(1)$ 知道答案，比如直接构造或计算最优解，就不属于 DP 范畴了。

DP vs. 记忆化搜索

可以说记忆化搜索就是 DP。

DP 是自底向上地按拓扑序计算。
而记忆化搜索是 自顶向下 的，从接受状态（汇点）开始反向在 DAG 上进行 DFS，只计算那些能到达汇点的路径上的节点，并用一个记忆化 memo 数组来避免重复访问（即重叠子问题）。

有些问题 不易判断哪些状态对答案真正有用 ，为减小无效状态，可以考虑记忆化搜索。经典的例子是 数位 DP。

计数 DP vs. 直接计数

计数问题的做法比较多，比如递推 (DP)、容斥反演等等，需要一些尝试，暂时没有什么好方法快速分辨。

最优化 DP vs. 网络流

这个是我最擅长的，有很多题目是一眼不可 DP 只能流。比如具有复杂的限制，而且是前后牵制的限制条件；或者是需要匀一匀找出判断是否有可行方案，但很难知道具体方案的。

例：2025 ICPC 西安 K。

Dijkstra 优化 DP： 当 DP 转移可以被看作图上的最短路问题时（例如，转移代价非负），Dijkstra 算法就可以用来替代常规的拓扑序递推，这在某些状态空间巨大但稀疏的 DP 问题中非常有效。

强制在线问题本质是对时间做扫描线，对于离线询问或者不涉及询问的问题，可以选取一个维度作为时间，做扫描线。

比如经典的二维数点、矩形面积并，都是将坐标轴的某个轴作为时间，用数据结构维护另一个轴。

我们知道线性 DP 可以支持修改操作，那么当然可以把 DP 的一个维度拿出来作为时间，动态维护 DP。

2024 ICPC 上海 F. Fast Bogosort

【题意】给定一个特定的随机排序算法：每次将序列切割成尽量多块，使得每一块内包含所有各自该有的数字，每一块独立区间 shuffle 后递归执行该算法。给定初始排列，求排序完成时区间 shuffle 次数的期望。 $N \leqslant 10^{5}$ 。

【简要分析】如果想怎么做分拆，就完全不可做。正确的做法是枚举分拆的第一分段点，把一个切 $k$ 刀的任务分解为切 1 刀 + 切 $k-1$ 刀，DP 求解。这里就体现了子问题重叠（资源复用）。

令 $g(n)$ 表示长度为 $n$ 不可分割的排列数量，有转移方程

g(n) = n! - \sum_{m=0}^{n-1} g(m) (n-m)!

令 $f(n)$ 表示长度为 $n$ 的随机排列的答案，

f(n) = 1 + \dfrac{1}{n!} \sum_{m=0}^{n} g(m) (n-m)! \Big(f(m) + f(n-m) - 1 \Big)

后面的优化不在本文讨论范围内。顺便一题，官方题解大力推式子，是最下策了。利用组合意义可以直接得到简洁的递推式。

DP 的实现

初始化 Initialization

这是写 DP 很容易挂的地方。

dp[0] 到底也是 0 还是 1？

状态设计技巧

按值 DP

刷表法 vs. 填表法

一种是枚举出边，一种是枚举入边

DP 方案回溯

有些最优化（含判定类）DP 问题不仅要输出答案，还需要给出方案。从图的角度考虑是，需要输出从起始状态（源点）开始，是走哪条路到达了接受状态（汇点）。

如果需要方案回溯，必须存储完整的历史状态记录，不能滚动数组优化。

方法有两种：

记录每个状态的最优转移是从哪里来（父节点是谁），这种方法最为简单粗暴，但需要额外开一个数组，占用空间大；
直接枚举可能的上一个状态的位置，这种方法需要额外的一倍时间，增加了时间常数。

经典 DP 模型

背包 DP

背包是一类最经典的 DP。如 01 背包，是把

背包问题还可以与多项式乘法结合

期望 DP

期望类 DP 兼具最优化 DP（需要做决策）与计数 DP（需要枚举所有可行情况）的特点。

一句话解释为什么要倒着 DP：你今天剩下的生活费会影响决策明天吃什么。要考虑对未来的影响，因此正着 DP 当然有后效性。

另一个关键点是理解期望形式的 Partition Theorem：

\mathbb{E}(Y) = \sum_{x} \mathbb{E}(Y \mid X = x) \mathbb{P}(X = x) .

有后效性的概率期望 DP

几何分布、高斯消元

2025 CCPC 女赛 H. 缺陷解码器

组合计数 DP

DP 优化

状态设计优化——状态压缩

状态压缩是 便于转移、优化时空 的一种思想。

标题不是状态压缩 DP，因为我不认为状态压缩与背包等相并列。

【HDU7842】
$n,m \leqslant 100, \ k \leqslant 20$ 。
设 f[i][j][pre][mul][cur] 表示走到 $(i, j)$ 格，已经结束的所有项之和为 pre，当前项的乘数为 mul，当前要计算的数字为 cur 的方案数，我们有一个 $\mathcal{O}(nmk^{3})$ 的 DP 做法。
这个东西需要开五维数组，写起来很丑。
方程其实可以分为两部分：前一部分 $i, j$ 是按照下标存的状态，后一部分为 pre, mul, cur 是按照值存的状态。我们可以对按值存的状态进行 状态压缩，并赋予一个 $0\sim k^{3}-1$ 的编号，那么下标可以直接取模，常数也减小了许多，也更加好写。

空间优化——滚动数组

滚动数组可以 优化空间复杂度，但不能优化时间复杂度。方案回溯问题不能滚动数组。

我们严格将转移分层，把所有第 $i$ 步的状态（例如，所有 dp[i][...] 节点）看作图的第 $i$ 层。如果计算第 $i$ 层的任意节点，其所依赖的所有节点（入边）都来自一个固定的、很近的邻域（比如只来自第 $i-1$ 层），就可以 只存储前几层的状态 f 和 当前层的状态 nf，以优化空间复杂度。

vector<int> f(M, inf);
for (int i = 0; i < N; i++) {
    vector<int> nf(M, inf);
    for (int j = A[i]; j < M; j++) {
        nf[j] = min(nf[j], f[j - A[i]] + W[i]);
    }
    f = move(nf);
}
cout << f[X] << '\n';