写在前面

1. ACM 训练（复习）的时候重新学习了一下常见的 DP 优化技巧，在学习的同时也有一些自己的理解，便一并总结在这。
2. 本文成文前阅读或参照了许多大佬的博客，这些将附在文末参考文献中。
3. 若文章中出现错误，烦请告知。感谢您的造访。

矩阵快速幂优化

主要是利用矩阵快速幂来优化一些线性递推问题。高维 DP 如果某一维状态较少也可以用矩乘优化。

这个比较普及不细讲，但是注意图的邻接矩阵也是可以用来矩阵加速的。

例题

• [HNOI 2011]数学作业
• [HNOI 2008]GT考试
• [POJ 3233]Matrix Power Series
• [USACO 07NOV]Cow Relays
• [SDOI 2009]HH去散步

前缀和优化

当转移碰到类似于 \(f_i=\sum\limits_{l\leq j\leq r}g_j\) 时，我们可以对 \(g\) 做一个前缀和，之后两端点差分即可。同时，其中求和式可换成 \(\min\) 或 \(\max\)，不过优化的适用条件更为苛刻。

另外多维 DP 有时也能用到前缀和优化，关键就是找到转移式有哪一个部分是只随着一个枚举变量变化而变化的，通过交换枚举顺序可以做到用前缀和优化。另外，要注意取的究竟是“前缀”还是“后缀”或是中间某两个端点，计算端点的值的时候要考虑交换 for 对循环范围的影响。[HEOI 2013]SAO这题可能会让你对这部分有充分了解。

例题

• [HAOI 2009]逆序对数列
• [HAOI 2008]木棍分割
• [HEOI 2013]SAO

未完待续

[总结]一些 DP 优化方法

原文：https://www.cnblogs.com/NaVi-Awson/p/12240616.html