OI-wiki 动态规划入门指南状态设计与状态转移方程的完整解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文以 OI-wiki 的《动态规划基础》章节docs/dp/basic.md为主体系统讲解动态规划Dynamic ProgrammingDP的基本思想、适用条件与两种经典模型——最长公共子序列LCS与最长不下降子序列LIS。读完本文后你将掌握状态—决策—状态转移方程—按阶段求解的完整 DP 建模流程能够独立推导 DP 递推式并理解从 $O(n^2)$ 到 $O(n\log n)$ 的 LIS 优化原理及其代码实现。文中所有算法均可在仓库 docs/dp/code/basic/ 中找到可直接运行的 C 与 Python 参考实现并有配套测试数据位于 docs/dp/examples/basic/。引入从数字三角形问题出发本页面通过一道经典例题引入动态规划的核心思想。给定一个 $r$ 行的数字三角形$r \leq 1000$需要找到一条从最高点到底部任意处结束的路径使路径经过的数字之和最大。每一步可以走到当前点左下方的点或右下方的点。例如7 3 8 8 1 0 2 7 4 4 4 5 2 6 5在上面的例子中最优路径是 $7 \to 3 \to 8 \to 7 \to 5$路径和为 $30$。为什么朴素枚举不可行最简单粗暴的思路是尝试所有可能的路径。由于每一步都有两种选择左下或右下路径条数是 $O(2^r)$ 级别的。当 $r 1000$ 时$2^{1000}$ 的数量级远远超出任何程序的承受能力因此这种暴力做法无法接受。关键观察最优决策的子结构性质注意到这样一个事实一条最优路径它的每一步决策都是最优的。以例题中的最优路径为例只考虑前四步 $7 \to 3 \to 8 \to 7$不存在一条从最顶端到第 $4$ 行第 $2$ 个数即值为 $7$ 的节点的权值更大的路径。对于每一个点它的下一步决策只有两种往左下角或者往右下角如果存在。因此只需要记录到达当前点的最大权值用这个最大权值执行下一步决策来更新后续点的最大权值。这样做还有一个额外的好处我们成功缩小了问题的规模将一个问题分成了多个规模更小的问题。要想得到从顶端到第 $r$ 行的最优方案只需要知道从顶端到第 $r-1$ 行的最优方案的信息即可。子问题重叠与记忆化此时还存在一个问题子问题间重叠的部分会很多同一个子问题可能会被重复访问多次效率仍然不高。解决这个问题的方法是把每个子问题的解存储下来通过记忆化的方式限制访问顺序确保每个子问题只被访问一次。上面就是动态规划的一些基本思路。下面的章节将更系统地介绍动态规划的思想、适用条件与建模方法。动态规划原理能用动态规划解决的问题需要满足三个条件最优子结构、无后效性和子问题重叠。最优子结构一个问题具有最优子结构是指问题的最优解由相关子问题的最优解组合而成。需要强调的是具有最优子结构的问题也可能是适合用贪心方法求解的最优子结构是动态规划的必要条件而非充分条件。在利用最优子结构进行证明时要注意确保我们考察了最优解中用到的所有子问题。经典的四步证明框架如下证明问题最优解的第一个组成部分是做出一个选择对于一个给定问题在其可能的第一步选择中假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的只是假定已经知道了这种选择给定可获得的最优解的选择后确定这次选择会产生哪些子问题以及如何最好地刻画子问题空间证明作为构成原问题最优解的组成部分每个子问题的解就是它本身的最优解。方法是反证法考虑若某个子问题的解不是其自身的最优解那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解从而得到原问题的一个更优的解这与原问题最优解的假设矛盾。在刻画子问题空间时要保持子问题空间尽量简单只在必要时扩展。最优子结构的不同体现在两个方面原问题的最优解中涉及多少个子问题确定最优解使用哪些子问题时需要考察多少种选择。从图论视角看子问题图中每个顶点对应一个子问题而需要考察的选择对应关联至子问题顶点的边。无后效性无后效性马尔可夫性指的是已经求解的子问题不会再受到后续决策的影响。也就是说一旦某个阶段的状态确定此后过程的演变只与此前各阶段的状态有关而与到达该状态的路径无关。这一性质保证了我们可以按阶段的先后顺序逐个求解而不必回头修改已经确定的子问题答案。子问题重叠动态规划之所以高效正在于它利用了子问题重叠如果有大量的重叠子问题我们可以用空间将这些子问题的解存储下来避免重复求解相同的子问题从而以空间换时间提升效率。这与前面提到的记忆化思想一脉相承。基本思路对于一个能用动态规划解决的问题一般采用如下思路解决将原问题划分为若干阶段每个阶段对应若干个子问题提取这些子问题的特征称之为状态寻找每一个状态可能的决策或者说是各状态间的相互转移方式——用数学的语言描述就是状态转移方程按顺序求解每一个阶段的问题。如果用图论的思想理解上述过程可以建立一个有向无环图DAG参见 docs/graph/dag.md每个状态对应图上一个节点决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长短路的问题详见 DAG 上的 DP。无后效性在此处的体现正是无环状态之间的转移方向确定不存在环状依赖。最长公共子序列LCS问题描述给定一个长度为 $n$ 的序列 $A$ 和一个长度为 $m$ 的序列 $B$$n,m \leq 5000$求出一个最长的序列使得该序列既是 $A$ 的子序列也是 $B$ 的子序列。关于子序列的定义可以参考 子序列。一个简要的例子字符串abcde与字符串acde的公共子序列有a、c、d、e、ac、ad、ae、cd、ce、de、acd、ade、ace、cde、acde最长公共子序列的长度是 $4$。状态设计与转移方程设 $f(i,j)$ 表示只考虑 $A$ 的前 $i$ 个元素、$B$ 的前 $j$ 个元素时的最长公共子序列的长度。求解 $f(i,j)$ 就是对应的子问题$f(i,j)$ 就是我们所说的状态而 $f(n,m)$ 是最终要达到的状态即为所求结果。对于每个 $f(i,j)$存在三种决策若 $A_i B_j$则可以将 $A_i$同时也是 $B_j$接到公共子序列的末尾得到 $f(i-1,j-1)1$若 $A_i \ne B_j$则只能选择跳过 $A_i$即 $f(i-1,j)$或跳过 $B_j$即 $f(i,j-1)$取两者较大值。状态转移方程如下$$ f(i,j)\begin{cases}f(i-1,j-1)1A_iB_j\\max(f(i-1,j),f(i,j-1))A_i\ne B_j\end{cases} $$注意该方程隐含了边界条件当 $i0$ 或 $j0$ 时$f(i,j)0$空序列与任何序列的最长公共子序列长度为 $0$。参考实现仓库 docs/dp/code/basic/lcs.cpp 中给出了 C 参考实现核心部分int n, m, a[MAXN], b[MAXM], f[MAXN][MAXM]; int dp() { for (int i 1; i n; i) for (int j 1; j m; j) if (a[i] b[j]) f[i][j] f[i - 1][j - 1] 1; else f[i][j] std::max(f[i - 1][j], f[i][j - 1]); return f[n][m]; }Python 实现见 docs/dp/code/basic/lcs.pydef dp(n, m, a, b): f [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i] b[j]: f[i][j] f[i - 1][j - 1] 1 else: f[i][j] max(f[i - 1][j], f[i][j - 1]) return f[n][m]从实现中可以看出程序以 $i$、$j$ 双层循环作为求解阶段每次转移只依赖 $f(i-1,j-1)$、$f(i-1,j)$、$f(i,j-1)$ 三个左上方的旧状态这正是无后效性的直接体现。数组下标从 $1$ 开始天然规避了 $i0$ 或 $j0$ 时的边界判断。仓库提供了对应的测试数据对 docs/dp/examples/basic/lcs.in 与 docs/dp/examples/basic/lcs.ans输入两序列1 3 4 5与2 1 3 5 7正确输出为3对应公共子序列1 3 5。复杂度与进阶该做法的时间复杂度为 $O(nm)$空间复杂度为 $O(nm)$。当 $n,m \leq 5000$ 时$O(nm)$ 的复杂度是可接受的。另外本题还存在 $O\left(\dfrac{nm}{w}\right)$ 的位运算加速算法利用 bitset 按字并行处理$w$ 为机器字长有兴趣的读者可以自行探索。最长不下降子序列LIS问题描述给定一个长度为 $n$ 的序列 $a$$n \leq 5000$求出一个最长的 $a$ 的子序列满足该子序列的后一个元素不小于前一个元素。注意不下降意味着相邻元素允许相等这与严格递增的最长上升子序列有细微差别后者将在算法二的注意事项中讨论。算法一$O(n^2)$ 动态规划设 $f(i)$ 表示以 $a_i$ 为结尾的最长不下降子序列的长度则所求答案为 $\max_{1 \leq i \leq n} f(i)$。计算 $f(i)$ 时尝试将 $a_i$ 接到其他最长不下降子序列后面以更新答案。于是可以写出这样的状态转移方程$$ f(i)\max_{1 \leq j i,~a_j \leq a_i} (f(j)1) $$即枚举所有在 $a_i$ 之前且不大于 $a_i$ 的元素 $a_j$把 $a_i$ 接到以 $a_j$ 结尾的最优子序列之后长度加 $1$ 后取最大值若不存在满足条件的 $j$则 $f(i)1$子序列只包含 $a_i$ 自己。仓库 docs/dp/code/basic/lis-1.cpp 中的 C 参考实现int n, a[MAXN], d[MAXN]; int dp() { d[1] 1; int ans 1; for (int i 2; i n; i) { d[i] 1; for (int j 1; j i; j) if (a[j] a[i]) { d[i] std::max(d[i], d[j] 1); ans std::max(ans, d[i]); } } return ans; }Python 实现见 docs/dp/code/basic/lis-1.py。容易发现该算法的时间复杂度为 $O(n^2)$当 $n \leq 5000$ 时足够高效但当 $n$ 达到 $10^5$ 级别时$O(n^2)$ 将无法承受需要算法二。算法二$O(n\log n)$ 贪心 二分当 $n$ 的范围扩大到 $n \leq 10^5$ 时第一种做法就不够快了下面给出一个 $O(n\log n)$ 的做法。合法状态判定考虑之前定义的状态 $(i, l)$表示序列以第 $i$ 个元素结尾的不下降子序列最长为 $l$。不同于以往按固定 $i$ 处理状态的方法这里直接判断 $(i, l)$ 是否合法初始状态 $(1,1)$ 必然合法对于任意 $(i, l)$如果存在 $j i$ 且 $(j, l-1)$ 合法同时 $a_j \le a_i$则 $(i, l)$ 合法。最终只需要找到合法状态中 $l$ 最大的 $(i,l)$即可得到最长不下降子序列的长度。维护数组 $d$设原序列为 $a_1, \cdots, a_n$定义数组 $d$其中第 $x$ 位表示长度为 $x$ 的不下降子序列的末尾元素的最小值。初始时序列为空。令 $i$ 从 $1$ 到 $n$ 遍历依次求出前 $i$ 个元素的最长不下降子序列的长度。对于当前元素 $a_i$如果 $a_i$大于等于序列 $d$ 中最后一个元素直接将元素 $a_i$ 插入到序列 $d$ 的末尾。解释若 $a_i$ 大于等于当前最长子序列的末尾元素说明存在一个不下降子序列可以接上 $a_i$不插入将破坏最优性。如果 $a_i$严格小于$d$ 中最后一个元素找到第一个大于它的元素并用 $a_i$ 替换它。解释若直接插在末尾会破坏 $d$ 的单调性替换操作可以保证每个长度的末尾元素尽可能小从而为后续元素保留更多可能性末尾元素越小越容易接上更大的元素。优化因为 $d$ 单调不减可用二分查找直接找到元素的插入位置将整体复杂度降低到 $O(n\log n)$而非暴力查找的 $O(n^2)$。输出具体子序列前驱回溯如果还要输出具体的最长不下降子序列可以额外维护数组 $d_x$表示长度为 $x$ 的不下降子序列中末尾最小元素的位置有多个时可任选一个。具体维护时只需要在插入元素 $a_i$ 到 $d_x$ 时同时更新 $dx$ 为 $i$ 即可。同时需要记录 $i$ 的最优前驱 $p_i$ 为 $d{x-1}$。最终从任意最大长度状态出发沿前驱 $p_i$ 回溯即可得到完整子序列。仓库 docs/dp/code/basic/lis-2.cpp 中的 C 参考实现完整地体现了上述三个数组的配合int n, a[MAXN], d[MAXN], di[MAXN], pre[MAXN], res[MAXN]; int dp() { int ans 0; for (int i 1; i n; i) { int tmp std::upper_bound(d, d ans, a[i]) - d; pre[i] tmp ? di[tmp - 1] : -1; d[tmp] a[i]; di[tmp] i; if (tmp ans) ans; } // Construct the subsequence. for (int k ans, i di[ans - 1]; k; --k) { res[k] a[i]; i pre[i]; } return ans; }对应 Python 实现见 docs/dp/code/basic/lis-2.py其中bisect.bisect_right(d, a[i], 0, ans)对应 C 的upper_bounddef dp(): ans 0 for i in range(1, n 1): tmp bisect.bisect_right(d, a[i], 0, ans) pre[i] di[tmp - 1] if tmp else -1 d[tmp] a[i] di[tmp] i if tmp ans: ans 1 # Construct the subsequence k ans i di[ans - 1] while k: res[k] a[i] i pre[i] k - 1 return ans算法的时间复杂度为 $O(n\log n)$输出答案回溯构造子序列的时间复杂度为 $O(\textit{ans})$其中 $\textit{ans}$ 为最长不下降子序列的长度。仓库提供的测试数据docs/dp/examples/basic/lis-2.in 与 docs/dp/examples/basic/lis-2.ans覆盖了多种边界情形输入序列长度输出子序列1 2 3 4 551 2 3 4 55 4 3 2 1112 2 2 2 2 262 2 2 2 2 23 1 2 2 4 3 551 2 2 3 542142注意第二组数据降序序列的最长不下降子序列长度仅为 $1$任意单个元素说明该算法正确区分了不下降允许相等与下降第三组数据2 2 2 2 2 2长度为 $6$验证了不下降子序列允许相等元素第四组数据输出1 2 2 3 5而非3 1 2 2 3 5或1 2 2 4 5验证了前驱回溯构造的正确性。注意最长上升子序列的差异对于最长上升子序列问题要求严格递增类似地可以令 $d_i$ 表示所有长度为 $i$ 的最长上升子序列的末尾元素的最小值。需要注意的是在替换步骤中若 $a_i \leq d_{len}$由于最长上升子序列中相邻元素不能相等需要在 $d$ 序列中找到第一个不小于$a_i$ 的元素用 $a_i$ 替换之。在实现上以 C 为例需要将upper_bound函数改为lower_boundPython 中对应将bisect_right改为bisect_left。这一处差异正是不下降与上升两类问题的本质区别所在。总结回顾整个章节动态规划的建模流程可以凝练为四步划阶段把原问题拆成按顺序求解的阶段定状态用状态刻画每个阶段子问题的特征如 LCS 的 $f(i,j)$、LIS 的 $f(i)$找决策、写转移明确每个状态如何由更小规模的状态转移而来写出状态转移方程按序求解依据无后效性按阶段顺序递推或记忆化搜索得到最终答案。两个例题分别展示了 DP 的两种典型形态LCS 是二维状态、依赖多个旧状态的经典模型LIS 则展示了从 $O(n^2)$ 朴素 DP 到 $O(n\log n)$贪心 二分 前驱回溯的优化路径。理解这两道题的建模与优化思路是后续学习区间 DP、树形 DP、状态压缩 DP 等进阶内容参见 docs/dp/index.md的基础。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考