【OI】动态规划（入门）

前言

咕咕咕，代码等会再补。

引入

例一

P1216

可以暴力枚举所有路径，这样的复杂度是 \(O(2^n)\)，不可接受。

正难则反，我们考虑逆推。首先一条路径的结尾一定是最后一行 \(n\) 个数中的某一个，而对于其中的某一个数，它只能从它正上方或者左上角的数走过来，我们显然希望它能从总和更大的位置走过来。推广一下，对于数字三角形中的每个点，我们都希望它从正上方和左上角两者中总和更大的一方走过来，这样才能满足每个点的路径最优。

因此，我们设 \(f_{i,j}\) 为从起点走到 \((i,j)\) 所经过路径上的数之和的最大值，根据我们的思路，有以下递推公式：

\[f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-1}\}+a_{i,j} \]

其中 \(f_{1,1}=a_{1,1}\)。

复杂度 \(O(n^2)\)。

例二

爬楼梯，有 \(n\) 阶楼梯，每次可以爬 \(1\) 或 \(2\) 阶，求从最底下走到最顶上的方案数。

同样考虑逆推，对于第 \(i\) 阶楼梯，它可以从第 \(i-1\) 阶走一步走上来，也可以从第 \(i-2\) 阶一步走上来。因此，可以设 \(f_i\) 为走到第 \(i\) 阶的方案数，根据加法原理，它满足递推公式：

\[f_i=f_{i-1}+f_{i-2} \]

其中 \(f_0=f_1=1\)。

复杂度 \(O(n)\)。

动态规划原理

在以上两个例题中，我们都用了一个思想：把大问题拆分成几个小的子问题，然后通过递归或递推的方式解决它。这种方法被称为动态规划（Dynamic Programming,DP）。例一中我们要求一个最值，这被称为最优化 DP，而第二位要求的是方案数，这被称为计数 DP。

可以使用动态规划解决的问题，必须满足以下三个特征：最优子结构、无后效性、重叠子问题。

最优子结构

回顾例一，我们发现 \((i,j)\) 的最优解由 \((i-1,j)\) 和 \((i-1,j-1)\) 的最优解得来，即一个问题的最优解可以由它的子问题的最优解组合而来，这个特征被称为最优子结构。需要注意的是，这个性质并不是动态规划专有的，也可能是贪心等其它方法可解决的问题。

无后效性

一个已求解的子问题，不会受到后续决策的影响，这一性质被称为无后效性。

重叠子问题

一个问题的子问题可能会重复出现。在例二中，如果使用递归求解，\(f(n)=f(n-1)+f(n-2)=f(n-2)+f(n-3)+f(n-2)\)，子问题 \(f(n-2)\) 会被重复计算。而动态规划则利用了重叠子问题的性质，将子问题的解存储起来以避免重复计算，从而达到优化复杂度的目的。

基本思路

在 DP 问题中，我们会采取以下一般过程求解：

1. 将问题划分成若干个阶段，每个阶段对应一些子问题，提取这些子问题的特征，这些特征被称为状态。

   在例一中，对于一个点 \((i,j)\)，它可以划分成 \((i-1,j)\) 和 \((i-1,j-1)\) 两个阶段，对应这两个子问题。而每个点的特征就是它的坐标，即 \((i,j)\)，因此我们设状态 \(f_{i,j}\) 表示点 \((i,j)\) 对应的最优解。

2. 寻找状态间的决策方式，或者说状态转移方式。

   根据最优子结构性质，满足递推公式：

   \[f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-1}\}+a_{i,j} \]

   这个公式又被称为状态转移方程，一般把等号换成 \(\leftarrow\) 表示状态转移的方向。

3. 按顺序求解每个阶段的问题。

   动态规划中有两种顺序：自顶向下和自底向上。自顶向上即为递归解决大问题时，通过递归把大问题拆分成小问题求解，再利用状态转移方程合并成大问题，往往需要通过记忆化搜索，即将重叠子问题存储来实现。自底向上则是先解决最小的子问题，再把子问题合并成大问题，一步步向上递推。两种方式需要先手动求出最底层的状态，这被称为边界条件，如例一中的 \(f_{1,1}=a_{1,1}\)。

本质上，我们把状态看成点，把状态转移的方向看成单向边，整个 DP 过程就形成了一张图，而根据无后效性，图上不存在环，因此这是一个 DAG。我们要求解的问题，其实就是求解 DAG 上的一条最短（长）路，而计数 DP 则是求解路径的数量。

例题

例一

给定两个序列 \(a,b\) 长度分别为 \(n,m\)，求两个序列的最长公共子序列（LCS）的长度。

设 \(f_{i,j}\) 为 \(a\) 序列只考虑前 \(i\) 个，\(b\) 序列只考虑前 \(j\) 个的 LCS 长度。如果 \(a_i=b_j\)，那么这两个元素显然接到前一个状态的末尾是最优的；否则我们可以考虑不管 \(a_i\) 或者不管 \(b_j\)，两种状态取较大值。可以写出下列状态转移方程：

\[f_{i,j}= \begin{cases} f_{i-1,j-1}+1 & a_i=b_j \\ \max\{f_{i-1,j},f_{i,j-1}\} & a_i \neq b_j \end{cases}\]

时间复杂度 \(O(nm)\)。

例二

给定序列 \(a\)，求它的最长上升子序列（LIS）长度。

设 \(f_i\) 为以 \(a_i\) 为结尾的 LIS 长度的最大值，答案显然为 \(\max_{i=1}^n f_i\)。 考虑转移，对于一个 \(j < i\)，如果 \(a_j<a_i\)，\(f_i\) 就可以由 \(f_j\) 转移而来，对所有满足条件的 \(f_j\) 取最大值，然后再加上 \(1\) 表示把 \(i\) 加入末尾即可，状态转移方程为：

\[f_i=\max_{1 \leq j <i}^{a_j < a_i} \{ f_j \}+1 \]

朴素做法时间复杂度为 \(O(n^2)\)，可以通过二分或者树状数组优化到 \(O(n \log n)\)。