dp 优化

温家浩 · 2023-08-07 18:49:56 · 个人记录

dp 优化

dp 优化基础理论

用动态规划解决问题具有空间耗费大、时间效率高的特点，但也会有时间效率不能满足要求的时候，如果算法有可以优化的余地，就可以考虑时间效率的优化。

DP高时间效率的关键在于它减少了“冗余”，即不必要的计算或重复计算部分，算法的几余程度是决定算法效率的关键。而动态规划就是在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少“冗余”。但是，一个动态规划问题很难做到完全消除“冗余”。

下面给出一般动态规划影响时间复杂度的三个因素：

\text{时间复杂度}=\text{状态总数}\times\text{每个状态转移的状态数}\times\text{每次状态转移的时间}

所以优化 dp 也通常可以从这三个方向入手。

关于“状态”的优化可以从很多角度出发，思维难度较高，有时候状态选择的好坏会直接导致算法在很大程度上的优劣。

dp 状态设计的优化，一般来讲都是优化状态的总数。当然为了方便决策与转移而重新设计状态也是可能的。令人遗憾的是，这类优化大多不具有通用性，优化方法因题而异，此处仅仅抛砖引玉，希望能给大家带来一定的启发。

例子
- 给定两个长度分别为 n,m 且仅由小写字母构成的字符串 A,B，求 A,B 的最长公共子序列。

矩阵优化 dp

矩阵的乘法是向量内积的推广。

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设 A 为 P\times M的矩阵，B 为 M\times Q 的矩阵，设矩阵 C 为矩阵 A 与 B 的乘积，其中矩阵 C 中的第 i 行第 j 列元素可以表示为：

C_{i,j}=\sum^M_{k=1}\,A_{i,k}\,B_{k,j}

矩阵乘法满足结合律，不满足一般的交换律。

利用结合律，矩阵乘法可以利用快速幂的思想来优化。

在比赛中，由于线性递推式可以表示成矩阵乘法的形式，也通常用矩阵快速幂来求线性递推数列的某一项。

例子一
- 题目描述
- 给出一张 n 个点（从 0 到 n-1 编号）m 条边有向图，q 次询问，每次询问求从 s t 恰好走 K 步到达 ed 的方案数，重边视作一条路径，每条边可重复走。
- 解法
- 设 f_{k}(i, j) 表示从点 i 到达点 j 恰好走 k 步的方案数。
- 若用邻接矩阵 a(i, j) 来表示点 i 与 j 之间是否连边，那么根据上述转移式子可得：
- 由于询问是不定向的，起点和终点可能是 [1, n] 中的任意一个，所以答案矩阵应包含 n^{2} 个信息，其中 F(k) 中的第 i 行第 j 列表示 f_{k}(i, j)，即用 F(K) 表示恰好走 K 步的答案矩阵。
- 所以对于每条边 (x, y)，使累乘矩阵中第 x 行第 y 列的数为 1，最后直接求一个 K 次幂即可。

F(k)=\left|\begin{array}{cccc} f_{k}(1,1) & f_{k}(1,2) & \ldots & f_{k}(1, n) \\ f_{k}(2,1) & f_{k}(2,2) & \ldots & f_{k}(2, n) \\ \ldots & \ldots & \ldots & \ldots \\ f_{k}(n, 1) & f_{k}(n, 2) & \ldots & f_{k}(n, n) \end{array}\right|

例子一的加强版
- 题目描述
- 给出一张 n 个点（从 0 到 n-1 编号）m 条边有向图，q 次询问，每次询问要么求从 s t 恰好走 K 步到达 ed 的方案数，要么求从 s t 走小于等于 K 步到达 ed 的方案数。重边视作一条路径，每条边可重复走。
- 解法
- 询问一同上，询问二的实质是求 ans^0+ans^1+\dots+ans^k，可以发现这就是等比数列求和！
  \begin{align} (ans^0+ans^1+\dots+ans^k)(1-ans)&=(1-ans)^k \\ (ans^0+ans^1+\dots+ans^k)(1-ans)(1-ans)^{-1} & =(1-ans)^k(1-ans)^{-1} \\ (ans^0+ans^1+\dots+ans^k)&=(1-ans)^{k-1} \end{align}
  用快速幂求出 (1-ans)^{k-1} 即可。
例子二（NOI2020 美食家）
- 题目描述
- 精灵王国共有 n 座城市，城市从 1 到 n 编号，其中城市 i 的美食能为小 W 提供 c_{i} 的愉悦值。精灵王国的城市通过 m 条单向道路连接，道路从 1 到 m 编号，其中道路 i 的起点为城市 u_{i}，终点为城市 v_{i}，沿它通行需要花费 w_{i}天。也就是说，若小 W 在第 d 天从城市 u_{i} 沿道路 i 通行，那么他会在第 d+u_{i} 天到达城市 v_{i}。
- 小 W 计划在精灵王国进行一场为期 T 天的旅行，更具体地，他会在第 0 天从城市 1 出发，经过 T 天的旅行，最终在恰好第 T 天回到城市 1 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第 0 天和第 T 天的城市 1），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将获得多次愉悦值。注意旅行途中小 W 不能在任何城市停留，即当他到达一座城市且还末结束旅行时，他当天必须立即从该城市出发前往其他城市。
- 此外，精灵王国会在不同的时间举办 k 次美食节。具体来说，第 i 次美食节将于第 t_{i} 天在城市 x_{i} 举办，若小 W 第 t_{i} 天时恰好在城市 x_{i}，那么他在品尝城市 x_{i} 的美食时会额外得到 y_{i} 的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的最大值。

数据结构优化 dp

例子（UVA12983 The Battle of Chibi）
- 题目描述
- 在一个长度为 n 的序列中找到长度为 m 的严格上升子序列的个数。n \leq 1000。
- 解法
- 方程应该是比较好推的，用 dp[i][j] 表示由序列中在 j 之前的数构成并以 a[j] 结尾的子序列中，长度为 i 的子序列的数量。则：
- 对于决策点 dp[i-1][k]，这里出现了 3 个信息：
  1. 在原序列中的位置 k<j 。
- 对于每一次 dp[i] 的决策，可以将 a[j] 作为数据结构维护的关键字，dp[i-1][j] 作为权值，加入 -inf 后离散化，得到一个大小为 N+1 的数组并在上面建立树状数组，每次计算 dp[i][j] 时查询前面已经加入的且关键字小于 a[j] 的 dp[i-1][k] 总和（即区间查询），然后把 dp[i-1][j] 加入树状数组（单点查询）。