前言本文选题都较为基?。鲇糜谡故居呕绞?nbsp;， 如果是要找题单而不是看基础概念 ， 请忽略本文 。
本文包含一些常见的dp优化（“√”表示下文会进行展示，没“√”表示暂时还咕着）：前缀和优化（√）、单调队列优化（√）、斜率优化（√）、四边形不等式优化、数据结构优化……
由于写本文主要是记录蒟蒻的dp优化学习过程，所以可能很不完善 ， 也会有很多错误 (?)。推荐看巨佬的：【学习笔记】动态规划—各种 DP 优化 - 辰星凌
1. 前缀和优化dp进行状态转移时，如果发现需加上前面的一类状态，就可以选择使用数组进行累计操作，以达到降维度的效果 。
1.1 P1521 求逆序对1.1.1 题目大意给出 \(n\) ， \(k\) ， 问 \(1..n\) 的排列中正好有 \(k\) 个逆序对的排列数 。
1.1.2 数据范围\(1 \leq n \leq 100\) ， \(1 \leq k \leq n * (n - 1) / 2\) 。
1.1.3 做法设 \(f_{i, j}\) 表示 \(1..i\) 的全排列中有 \(j\) 个逆序对的排列数 。答案即为 \(f_{n, k}\) 。
考虑在 \(1..(i-1)\) 的排列中加入一个 \(i\) 所能贡献的逆序对数量 。由于 \(i\) 是最大的 ， 故当它被排在第 \(j\) 个时 ， 相应的逆序对数量会增加 \(i - j\) 个 。
不难列出转移式：\(f_{i, j}=\sum_{k = 0}^{min(j, i - 1)}f_{i - 1, j - k}\) 。
其中的 \(k\) 表示新增的逆序对数 。
同时初始化 \(f_{1, 0}=1\) 。
由于此题比较水 ， 所以不优化也能过 。
const int N = 110, mod = 10000;int n, k, f[N][N * N >> 1];int main() { n = read(), k = read(); f[1][0] = 1; for (int i = 2; i <= n; i++)for (int j = 0; j <= (i * (i - 1)) >> 1; j++)for (int k = 0; k <= min(j, i - 1); k++)f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod; printf("%d\n", f[n][k]); return 0;}接下来开始优化 。
现在把上面转移的式子改一下 ， 方便优化：
\(f_{i, j}=\sum_{k = max(0, j - (i - 1))}^jf_{i - 1, k}\) ， 相应的，代码可以改成这样：
for (int i = 2; i <= n; i++)for (int j = 0; j <= (i * (i - 1)) >> 1; j++)for (int k = max(0, j - (i - 1)); k <= j; k++)f[i][j] = (f[i][j] + f[i - 1][k]) % mod;开数组 \(s_{i, j}=\sum_{k = 0}^jf_{i, k}\)，那么 \(s_{i, j}=s_{i, j - 1}+f_{i, j}\)。
相应的，转移式变为 \(f_{i, j}=s_{i - 1,j}-s_{i - 1, j - (i - 1) - 1}\)，注意边界问题 。
for (int i = 1; i <= n; i++) f[i][0] = s[i][0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= (i * (i - 1)) >> 1; j++)s[i - 1][j] = (s[i - 1][j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= (i * (i - 1)) >> 1; j++)f[i][j] = (s[i - 1][j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[i - 1][j - (i - 1) - 1])) % mod; }注意到 \(s\) 数组的前一维似乎没有什么用处，考虑使用滚动数组继续优化 。
for (int i = 1; i <= n; i++) f[i][0] = 1; s[0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= (i * (i - 1)) >> 1; j++)s[j] = (s[j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= (i * (i - 1)) >> 1; j++)f[i][j] = (s[j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[j - (i - 1) - 1])) % mod; }1.2 P2513 [HAOI2009]逆序对数列1.2.1 题目大意给出 \(n\)，\(k\)，问 \(1..n\) 的排列中正好有 \(k\) 个逆序对的排列数 。
1.2.2 数据范围\(1 \leq n, k \leq 1000\) 。
1.2.3 做法乍一眼看是不是和上题一模一样 。
如果直接提交上题的代码（改了数据范围），就会得到30分的好成绩 。（最后几个点全部MLE）
稍稍计算一下，就会发现 \(499500000\) 的 int 数组是不是有那么亿点点大？
那么如何优化代码呢？
注意到上题的代码中，逆序对数枚举的上限为 \(\frac {n \times (n-1)} {2}\)，再瞅一眼本题数据范围，最大逆序对数只有 \(1000\)？！
不难想到改成以下代码：
const int N = 1010, mod = 10000;int n, k, f[N][N], s[N ];int main() { n = read(), k = read(); for (int i = 1; i <= n; i++) f[i][0] = 1; s[0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= min((i * (i - 1)) >> 1, k); j++)s[j] = (s[j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= min((i * (i - 1)) >> 1, k); j++)f[i][j] = (s[j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[j - (i - 1) - 1])) % mod; } printf("%d\n", f[n][k]); return 0;}真好，既优化了空间又优化了时间 。
2. 单调队列优化dpOI-Wiki 传送门
借助单调队列的单调性，及时排除不可能的决策 ， 保持候选集合的高度有效性和秩序性 。
单调队列尤其适合优化决策取值范围的上、下界均单调变化，每个决策在候选集合中插入或删除至多一侧的问题 。
推荐阅读
- 梦幻西游搬砖赚钱方式（梦幻西游搬砖如何月入3000)
- 灵域境界等级划分_灵域各种等级势力介绍
- 基于PL022 SPI 控制器 海思3516系列芯片SPI速率慢问题深入分析与优化
- 我的世界创造模式怎么骑马，骑马方式详解（在我的世界里面怎么教我们骑马)
- 云计算_OpenStack
- zip怎么设置默认打开方式（怎么更换zip打开方式)
- Vue3 SFC 和 TSX 方式调用子组件中的函数
- 九重试炼免广告卷获取方式是什么
- 怎么在线预览.doc，.docx，.ofd，.pdf，.wps，.cad文件以及Office文档的在线解析方式。
- 京东云TiDB SQL优化的最佳实践