看到很多讲动态规划的文章，随便讲讲一些自己的看法。限于作者水平，如有不足，欢迎指正。

1. 动态规划

首先，什么是动态规划？显然，在竞技性编程语境下的“动态规划”的含义并不局限于最优化问题的某种解决方法。比如计算Fibonacci序列第$n$项，就和"最优"没有什么关系。

笔者的水平不足以对动态规划下一个较为严谨的定义，但是可以说：通常，竞技性编程中的动态规划主要关心两件事情——状态的定义，状态转移方程。

先从一个最基础也最重要的问题开始：DAG（有向无环图）最长路问题。

在这个问题中，可以把状态定义成$F(u)=$以$u$最为终点的所有路径中的最长路长度。这里的状态其实就是指的某个子问题（的解）。如果确定状态的定义，那么状态转移方程也就可以自然得到：$F(u)=\underset{(v,u)\in E}{\max }(F(v)+w(v,u))$。当然，这里还有两个小细节：如果点$u$入度为$0$，那么$F(u)=0$，可以将这种不依赖于其他状态而得到值的状态叫做初始状态；原问题的答案是$\underset{u\in V}{\max }F(u)$。

在这个问题中，状态恰好是图中的点，初始状态恰好是图中入度为零的点，转移关系恰好是图中的边。其实，对于更一般的动态规划问题，都可以简单抽象成DAG上的递推问题。

比如最长公共子序列问题，状态的定义是$F(i,j)=s[1\dots i]$和$t[1\dots j]$的最长公共子序列长度。状态转移方程是$F(i,j)=\{\begin{array}{ll}F(i-1,j-1)+1,& s[i]=t[j],\\ \max (F(i-1,j),F(i,j-1)),& s[i]\ne t[j].\end{array}.$

不妨定义$s[1\dots 0]$为空串，那么初始状态为$F(i,j)=0,\text{if }ij=0$。原问题的答案是$F(|s|,|t|)$。

如果将每个状态用点表示，将状态转移方程右侧出现的状态往左侧出现的状态连边，那么就可以得到一个DAG，并且每个点的值依赖于它的所有入点的值。例如令$s=$“$abc$”，$t=$“$bbc$”，可以得到如下的DAG。

$\begin{array}{ccccccc}(0,0)& \to & (0,1)& \to & (0,2)& \to & (0,3)\\ \downarrow & & \downarrow & & \downarrow & & \downarrow \\ (1,0)& \to & (1,1)& \to & (1,2)& \to & (1,3)\\ \downarrow & \searrow & \downarrow & \searrow & \downarrow & & \downarrow \\ (2,0)& \to & (2,1)& \to & (2,2)& \to & (2,3)\\ \downarrow & & \downarrow & & \downarrow & \searrow & \downarrow \\ (3,0)& \to & (3,1)& \to & (3,2)& \to & (3,3)\end{array}$

2. 方案输出

为了方便，定义形如以下的式子叫做状态转移方程：
$F(u)=S(\{I(u)\}\cup \{G(e,F(e.\text{from})):e.\text{to}=u,e\in E\})$.

解释一下每个字母的含义$F(u)$是状态$u$的值；$S$一般是求和函数，最大值函数或者最小值函数；$I$是指状态$u$可能存在的不依赖于其他状态的值;$G$是状态转移函数，可以通过$u$的所有入边转移到$u$。

例如在DAG最长路问题中，$S$是最大值函数，$I(u)=0$，$G(e,F(e.\text{from}))=F(e.\text{from})+w(e)$.

对于有些需要输出最优方案的最优化问题，需要记录决策。有了上面的记号，就可以定义（最优）决策：使得$F(u)=G(e,F(e.\text{from}))$的$e$，也就是说，$F(u)$的取值是从$e$这条边转移得到的。注意，一个状态可能有多个决策。如果在计算每个状态的取值时记录决策，就可以在可以作为最优解的状态沿着决策边反向到达一个初始状态从而得到最优方案。

有些时候，为了输出某种方案，需要修改状态的定义：如求DAG字典序最小的最长路。这个时候就需要将态定义为$F(u)=$以$u$最为起点的所有路径中的最长路长度，这样从某个字典序最小的可以作为最优解的点出发，沿着字典序最小的决策边到达初始状态，就时字典序最小的最长路。

3. 实现方法

许多初学者喜欢使用记忆化搜索来解决动态问题。沿用上面的记号，很容易写出记忆化搜索的（C++）代码，其中$E_{\text{in}}[u]$表示$u$的所有入边。

map<Status, Type> f;
Type F(Status u){
    if(f.count(u)) return f[u];
    f(u) = I(u);
    for(Edge e : E_in[u])
        f[u] = S(f[u], G(e, f[e.from]));
    return f[u];
}

另外一种方法时使用（显式或非显式的）拓扑序:

map<Status,Type> f;
vector<Status> topological_order;
for(Status u : topological_order){
    f(u) = I(u);
    for(Edge e : E_in[u])
        f[u] = S(f[u], G(e, F(e.from)));
}

通常，可以直接得到拓扑排序，例如在最长公共子序列中，可以直接用下面代码得到其中一种合法的拓扑序。

for(int i = 1; i <= s_size; i += 1)
    for(int j = 1; j <= s_size; j += 1){
        //...
    }

这类拓扑序满足$(x_1,x_2,\cdots ,x_n)\le (y_1,y_2,\cdots ,y_n)$当且仅当对于每个$i,x_i\le y_i$的问题，可直接按字典序排序。而在有些比较复杂的问题中，的确需要通过拓扑排序的方法来得到正确的拓扑序。

一般来说，基于拓扑序的方法会比记忆化搜索有更好的效率。但在某些特殊的情况下，记忆化搜索会有更好的效率。例如，某些问题只需要求出某个终点状态的值，并且不是所有状态都存在一条到终点状态的路径，以及难以直接找到这些状态，使用记忆化搜索可以忽略掉这些状态，从而有更好的效率。

一些无关紧要的内容：

在基于拓扑序的方法中，还分为两种流派，这两种流派没有一个公认的命名。这里暂且称为主动式转移和被动式转移。前面提到的的代码就是被动式转移，下面的代码就是主动式转移：

map<Status,Type> f;
vector<Status> topological_order;
for(Status u : topological_order) f[u] = I(u);
for(Status u : topological_order)
    for(Edge e : E_out[u])
        f[e.to] = S(f[u], G(e, f[u]);

这两种流派相当于大括号是否换行，可以有效在团队比赛中引起队内矛盾。

4. 优化方法

限于篇幅，随便讲几种常见的。并且这里只是随便谈谈，并不会介绍它们的具体内容。

滚动数组。在竞技性编程中，通常认为在1s内可以执行$10^8$级别次的整数四则运算，但是$10^8$个int变量需要大约800MB的内存，而有些比赛中只会提供128~512MB的内存。简单点地说，有一部分动态规划的问题内存显示是比时间限制要紧的。使用滚动数组，通常是将形如$O(nm)$的空间复杂度降低到$O(m)$，同时时间复杂度为$O(nm)$不变。

矩阵乘法。有一类动态规划问题可以在没有初始值的情况下用矩阵乘法表示从一个点到另一个点的转移方程。通常应用在两种问题上，一种是状态数非常大需要使用矩阵快速幂优化的问题，一种是结合线段树等数据结构完成修改-询问类型的基于动态规的划问题。

数据结构。在动态规划的转移中，有些时候需要通过维护数据结构来不枚举所有入边而直接从数据结构中得到当前状态的值，通常使用的数据结构有平衡二叉搜索树、线段树、树状数组、单调队列、单调栈等等。还有一种特殊的“数据结构”就是凸包，也有人称这种方法为斜率优化。

bitset。在一类动态规划问题中，可能会有数倍于时间限制或内存限制的方法。如在不超过$50000$个点和$50000$条边的DAG上，对每个点$u$，分别求出有多少个点可以到达点$u$。令状态为$F(u)$=所有可以到达点$u$的点的集合，需要$O(nm)$的总时间完成转移，使用bitset表示集合可以使得（时间和空间）复杂度变为$O(\frac{nm}{w})$其中$w$是机器字节位长，现在通常为$64$位。

决策单调性。在一类序列问题中，具体地说，形如$F(u)=\underset{\text{v<u}}{\max }G(u,v,F(v))$，记$P(u)=\min \{v:G(u,v,F(v))=F(u)\}$为决策点，如果满足对于所有$v\le u$有$P(v)\le P(u)$，则称为问题具有决策单调性，通常可以结合分治来优化复杂度。

启发式（按秩）合并。在一类树问题中，每个点需要求解的值是一个大小和子树大小相当的数据结构（通常是平衡二叉搜索树或者数列），可以将其最大的子树的集合直接浅拷贝给它本身。通常在英文中叫做DSU on tree，因为这种方法最常见于DSU（并查集）中。

5. 常见模型

最后，提一下几种经典问题和常见模型。

• LIS（最长上升子序列），复杂度$O(n\log n)$。
• LCS（最长公共子序列），复杂度$O(nm)$。
• TSP（旅行商问题），复杂度$O(n^2{2}^n)$。
• 背包问题。
• 数位DP。如求$1$~$n$中所有回文数字，复杂度可以为$O(d\log n)$，$d$为进制。
• 树DP。如求包含每个点的连通子图数量，复杂度$O(n)$。
• 有限自动状态机作为一维状态的问题。如给定一个自然数集合$set$，问$1$~$n$里有多少数包含（在字符串意义下）其中至少一个$set$中的数，复杂度可以为$O(|s|d\log n)$ ，$|s|$为AC自动机状态数。

最后的最后，如果有一些遗漏的并且非常重要的内容，欢迎补充。