第十三章 动态规划的引入

• 什么是动态规划
  • 例1：纸币问题
  • 例2：P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
• 状态、转移与有向无环图
  • 例3：纸币问题2
  • 例4：纸币问题3
  • 例5：P1048 [NOIP2005 普及组] 采药
  • 例6：P2196 [NOIP1996 提高组] 挖地雷
• 拓扑序与记忆化搜索
  • 例7：P1434 [SHOI2002] 滑雪
  • 例8：P4017 最大食物链计数
• 动态规划的解法
  • 例9：P1115 最大子段和
  • 例10：整数划分

遇到 “求最佳方案” 的问题，可以考虑使用贪心算法在每步决策时使用单步最佳方案，或者使用枚举（搜索）算法枚举所有可能的角色。使用贪心算法的问题是 “目光短浅”，不一定可以站在全局的角度来统筹决策，可能会出现结果并不是全局最佳的；而使用枚举搜索算法，虽然可以遍历所有的可能，但如果数据量稍大，就可能超时。这个时候可以考虑使用动态规划解决这些问题。

动态规划的核心是 “状态缓存”，将一个状态的统计结果传递到另外一个状态，这有一点类似递推算法。

什么是动态规划

例1：纸币问题

某国有 $n (n \le 1000)$ 种纸币，每种纸币面额为正整数 $a_i$ 并有无限张，试问使用至少多少张纸币可以凑出 $w (w \le 10000)$ 的金额。

结合了搜索与固定答案的思想的算法，称之为记忆化搜索。

    f[0] = 0;
    for (int i = 1; i <= w; i++) {
        f[i] = inf;
        for (int j = 1; j <= n; j++) {
            if (a[j] <= i) {
                f[i] = std::min(f[j], f[i - a[j]] + 1);
            }
        }
    }

通过把原问题分解成若干相关子问题（所有这些问题在一定意义上答案固定），再利用已知子问题的答案依次计算未知问题答案，最终得到原问题答案的方式，称之为动态规划（$\text{Dynamic Programming}$，简称 $\text{DP}$。

例2：P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

    for (int i = n; i > 1; i--) {
        for (int j = 1; j <= i - 1; j++) {
            f[i - 1][j] += std::max(f[i][j], f[i][j + 1]);
        }
    }

状态、转移与有向无环图

动态规划的状态可以笼统的解释成 “问题所在的局面”。某状态、某局面、某状态表示的答案（的值），某状态代表的方案（集合），某状态代表的有向无环图上的点，在本质上连通，有时会用一个字母表示。

可以看到，状态转移具有明确良好的定义，一般可以写成：（用变量表示的）所在局面的（最优）答案，或者满足某中性质的方案数。

状态的答案应该只依赖于状态定义的局面和一些状态以外的常量。也就是说，在一般情况下，状态变化并不会影响状态以外的变量，该状态之后的演变不受这个状态之前决策的影响，因此如果要用动态规划来解决一道题，请把所有可能的变动加入到状态的定义中去。

因为要求解最终状态的答案，所以状态之间需要存在某些关系。一般把这样的计算关系称作转移，计算式称为（状态）转移方程。

可以看到，只有依据正确的状态定义和状态转移方程，才可以有理有据地做对一道题。

状态转移方程一般具有它自己的意义，体现的是从一个状态到另一个状态到变化。

对于最优化问题来说，转移方程的目的就是找到最优的前继情况的答案。在无特殊性质的情况下，转移方程需要找出所有前继情况并取出最优答案。

注意，若前继状态的最优答案不能转移成为当前状态的最优答案，则该问题（至少目前这个定义的状态）不满足用动态规划解决的要求。前继状态最优解与当前状态之间最优解的关联性被称为动态规划的最优子结构性质。

对于计数问题来说，转移方程的目的就是不遗漏不重复地统计局面的所有方案数。一般来说，转移方程需要找出所有前继情况并进行恰当的组合计数。

值得一提的是，转移存在两种方式，一种是发送型枚举，一种是接受型枚举。前者枚举状态的后继，并计算对后继的贡献；后者枚举状态的前继，当即计算出状态的答案。两种转移方式的选取主要取决于枚举前后继状态的难度和转移的复杂程度。不同的题用了恰当的转移方式，代码编写难度会显著下降。

$\text{DAG}$ 是一种表示 “依赖关系” 的图，在动态规划中，依赖关系体现为 “一个局面可以从哪些局面转移过来”。这里不容许 “互相依赖” 的情形发生：一旦两个局面可以互相到达，那么这个问题（至少目前这个定义的状态）不具备用动态规划解决的性质。

状态间不能互相到达的性质以及未来与过去无关的性质统称为动态规划的无后效性。

把动态规划的状态和转移与 $\text{DAG}$ 的点和边建立对应关系。因为转移顺序的需要，有时题意中的 $\text{DAG}$ 与 $\text{DP}$ 建模时 $\text{DAG}$ 的边恰好是相反的，即所谓 “自底向上”。由于有向无环图具有严格的依赖性质，这要求处理每个状态时，必须先处理完它的前继状态。哪些没有前继状态（或前继相对不完全）的状态称为边界状态。

按照拓扑序遍历图就能保证当前状态的前继状态全部被遍历过，恰好解决了这个问题。当然对于绝大多数动态规划问题来说，拓扑序时明显的，有时还是分层的。有时，把这种明显的层次称为阶段。

阶段的含义呼之欲出，它体现了一种步骤，只要按照步骤执行，整个问题可以有条不紊地（按照拓扑序）被解决。同时阶段也和状态的定义紧密相关。只要找到了正确的阶段，就不需要刻意建图寻找拓扑序，只要按照某种相对简单的顺序遍历整个状态数组即可。

例3：纸币问题2

您有 $n (n \le 1000)$ 种面额互不相同的纸币，每种纸币面额为 $a_i$ 并有无限张，您需要支付 $w (w \le 10000)$ 的金额，请问有多少种方式。这里同样的纸币组合，支付顺序不一样视作不同方案。输出答案对于 $1000000007$ 取模的结果。

    f[0] = 1;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= a[j]) {
                f[i] = (f[i] + f[i - a[j]]) % mod;
            }
        }
    }

例4：纸币问题3

有 $n (n \le 1000)$ 种纸币，每种纸币面额为 $a_i$ 并有无限张，试问有多少种纸币组合可以凑到 $w (w \le 10000)$ 的金额。输出答案对于 $1000000007$ 取模的结果。

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= w; j++) {
            f[j] = (f[j] + f[j - a[i]]) % mod;
        }
    }

例5：P1048 [NOIP2005 普及组] 采药

    for (int i = 1; i <= M; i++) {
        for (int j = T; j >= a[i]; j--) {
            f[j] = std::max(f[j], f[j - a[i]] + v[i]);
        }
    }

这类具有多个物品可选，又有一定（体积）限制的问题模型称作背包问题。背包问题时动态规划最基础的模型之一。所有物品只有一件的模型被称为 $\text{0-1}$ 背包，所有物品可以选择任意多次的模型被称为完全背包。

例6：P2196 [NOIP1996 提高组] 挖地雷

   for (int i = 1; i <= N; i++) for (int j = 0; j < i; j++) {
        if (f[i] < f[j] + a[i] && b[j][i]) {
            f[i] = f[j] + a[i];
            g[i] = j;
        } 
    }

拓扑序与记忆化搜索

例7：P1434 [SHOI2002] 滑雪

int DFS(int x, int y) {
    if (x < 1 || x > n) return 0;
    if (y < 1 || y > m) return 0;
    if (f[x][y] != -1) return f[x][y];
    int ret = 0;
    for (int i = 1; i <= 4; i++) {
        int xx = x + dx[i];
        int yy = x + dy[i];
        if (a[x][y] > a[xx][yy]) ret = std::max(ret, DFS(xx, yy));
    }
    return f[x][y] = ret + 1;
}

例8：P4017 最大食物链计数

int DFS(int u) {
    if (f[u]) return f[u];
    int ret = 0;
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        ret = (ret + DFS(v)) % mod;
    }
    return f[u] = ret;
}

int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        std::cin >> u >> v;
        graph::addEdge(v, u);
        graph::vertex[u].outDegree++;
        graph::vertex[v].inDegree++;
    }
    for (int i = 1; i <= n; i++) if (graph::vertex[i].inDegree == 0) f[i] = 1;
    for (int i = 1; i <= n; i++) graph::DFS(i);
    for (int i = 1; i <= n; i++) if (graph::vertex[i].outDegree == 0) ans = (ans + f[i]) % mod;
    std::cout << ans;
    return 0;
}

用记忆化搜索，可以无视拓扑排序便捷地求解问题。

动态规划的解法

例9：P1115 最大子段和

    for (int i = 1; i <= n; i++) {
        f[i] = std::max(0, f[i - 1]) + a[i];
        ans = std::max(ans, f[i]);
    }

例10：整数划分

将 $n (n \le 50000)$ 分为若干个不同整数的和，有多少种不同的划分方式，由于数据较大，输出对 $10^9 + 7$ 取模的结果。

    f[0][0] = 1;
    for (int i = 1; i <= 317; i++) {
        for (int j = i; j <= n; j++) {
            f[i][j] = (f[i - 1][j - i] + f[i][j - i]) % mod;
        }
        ans = (ans + f[i][n]) % mod;
    }

技术问题的转移与方案的生成方式紧密相关，有利的生成方式会带来意想不到的优化。

一旦定义出了这个状态，并且想到了这个巧夺天工的转移，所有的问题就迎刃而解。

一道动态规划题目会不可避免地涉及阶段、状态、转移、性质、优化等多个概念。

1. 读题：阅读题目信息。
2. 寻找阶段/性质：对简单题来说要在体面中寻找可能可以称为阶段的量。对较复杂的体则需要寻找一些性质来支撑转移或者状态设计。
3. 构造状态：用之前找到的阶段或性质来构造状态。定义状态的通常形式：$[(用变量表示的)缩在局面]的[(最优)答案/满足某种性质的方案数]$。注意这里的状态需要满足重叠子结构性质。
4. 设计转移：依靠定义的状态以及题意来写出状态之间的转移关系。对最优化题来说是最优解的转移关系；对计数题来说是组合计数关系。
5. 边界值：边界点通常有两类。一是先验答案点，即答案由题意确定的点，一般是作为整张 $\text{DAG}$ 的起点。二是不完全转移点，即对于一般的转移方程可能会出现越界情况的点。这两类点的处理需要注意规避错误，特别是后一种比较难查错。
6. 优化：动态规划的优化是一门深奥的学问。在信息学竞赛中可能可以碰到的优化方式包括（但不限于）状态优化、转移优化、数据结构加速、单调性优化（斜率优化、四边形不等式）、$\text{FFT}$ 加速、反演计数、根号分治、$\text{CDQ}$ 分治。对于计数问题和最优化问题通常有着不同的优化思路。