![](https://csdnimg.cn/release/download_crawler_static/86323375/bg1.jpg)
算法竞赛专题解析
--
动态规划优化(1)--四边形不等式
罗勇军
2020.3.27
本系列是这本书的扩展资料:《算法竞赛入门到进阶》(京东,当当) 清华大学出版社
本文
web
地址(同步):
https://blog.csdn.net/weixin_43914593
https://www.cnblogs.com/luoyj/
PDF
下载地址:
https://github.com/luoyongjun999/code
其中的补充资料
如有建议,请联系:(
1
)
QQ
群,
567554289
;(
2
)作者
QQ
,
15512356
《算法竞赛入门到进阶》的第 7 章“动态规划”,讲解了 DP 的概念,以及线性 DP、区间
DP、树形 DP、数位 DP、状态压缩 DP 等应用场景。
本文以及后续几篇,将介绍 DP 的优化技术。
1.1 四边形不等式 DP 优化
四边形不等式 DP 优化涉及的证明比较复杂,如果先给出定义和证明会让人迷惑,所以本
文的组织结构是:先给出应用场景,引导出四边形不等式的概念,再进行定义和证明,最后用
例题巩固。
四边形不等式 DP 优化,虽然理论有点复杂,但是编码很简单。
1.1.1 理论背景
四边形不等式(quadrangle inequality)应用于 DP 优化,是一个古老的知识点。它起源于
Knuth(高纳德)1971 年的一篇论文
①
,用来解决最优二叉搜索树问题。1980 年,储枫(F. Frances
Yao,姚期智的夫人)做了深入研究
②
,扩展为一般性的 DP 优化方法,把一些复杂度 O(n
3
)的
DP 问题,优化为 O(n
2
)。所以这个方法又被称为“Knuth-Yao DP Speedup Theorem”。
1.1.2 应用场合
有一些常见的 DP 问题,通常是区间 DP 问题,它的状态转移方程是:
dp[i][j] = min(dp[i][k] + dp[k + 1][j] + w[i][j])
其中 i <= k < j,初始值 dp[i][i]已知。min()也可以是 max(),见本文第 6 小节的说明。
方程的含义是:
(1)dp[i][j]表示从 i 状态到 j 状态的最小花费。题目一般是求 dp[1][n],即从起始点 1 到
终点 n 的最小花费。
(2)dp[i][k] + dp[k + 1][j]体现了递推关系。k 在 i 和 j 之间滑动,k 有一个最优值,使得
dp[i][j]最小。
(3)w[i][j]的性质非常重要。w[i][j]是和题目有关的费用,如果它满足四边形不等式和单
调性,那么用 DP 计算 dp 的时候,就能进行四边形不等式优化。
这类问题的经典的例子是“石子合并”
③
,它的转移矩阵就是上面的 dp[i][j],w[i][j]是从第 i
①
Donald E. Knuth. Optimum binary search trees. Acta Informatica, 1:14–25, 1971.
②
F. Frances Yao. Efficient dynamic programming using quadrangle inequalities. In Proceedings of the 12th Annual
ACM Symposium on Theory of Computing, pages 429–435, 1980.
论文下载:http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p429-yao.pdf
③
参考《算法竞赛入门到进阶》7.3 节 区间 DP,“石子合并”问题。