【算法讲解】dp优化——四边形不等式优化-爱代码爱编程

2023-05-24 分类: 算法讲解算法

前言

此优化策略由高德纳和姚期智发现并证明，故学名称之为 Knuth-Yao Speedup
(Knuth 是算法届的鼻祖，对于算法新手来说，KMP一定不陌生，Knuth 就是三个联合发明人之一的 K；Yao 就是清华姚班的姚期智)
证明过程中依赖四边形不等式，所以也俗称四边形不等式优化，
适用于当 dp 方程、转移函数符合一定特征时，可以将复杂度降低一个维度
属于非常难的 dp 优化，Codeforces 中需要应用此类优化的题目至少是 2400 分以上
证明非常困难，如果前置没有掌握这个知识点，遇到相应的题是无论如何都做不出的

背景

最初发明这个算法的动机，是为了解决最佳二叉搜索树(Optimal Binary Search Tree)问题(OBST 会在其他文章中详细介绍，此处不展开)
朴素的 OBST 问题的解法是 $O(n^3)$
Knuth 在1971发现发现当符合某种条件下（见下文的DP策略优化），可以让复杂度降为 $O(n^2)$

$\le opt(i,j) \le opt(i+1,j)$

Yao 在1980年进一步发现下文的推论2和推论3：

$c (i, j)$ 符合四边形不等式 $\Longrightarrow dp(i,j)$ 也符合四边形不等式
$d p (i, j)$ 符合四边形不等式 $\Longrightarrow opt(i,j-1) \le opt(i,j) \le opt(i+1,j)$

既只要 $c (i, j)$ 符合四边形不等式，就可以将 OBST 的复杂度降低到 $n^2)$

问题描述

我们将问题简化，就不直接从 OBST 开始推演，直接给出 dp 方程，OBST 到 dp 方程的推演会在其他文章中介绍

对于下述 dp 方程， $d p (l, r)$ 代表状态， $c (l, r)$ 代表状态转移的代价 cost（ $O (1)$ 的复杂度可以计算得到）
$\left\{ \begin{aligned} \min \limits_{k\in [l,r)}\{dp(l,k) + dp(k+1,r)\} + c(l,r),l<r \\ 0,l=r \\ \infty,l>r \end{aligned} \right.$
用朴素的方式直接实现，因为有 $O(n^2)$ 个状态，每次状态转移需要从 $l$ 遍历到 $r$ ，也就是 $O (n)$ 的开销，所以整体复杂度是 $O(n^3)$

但是如果 $c (l, r)$ 满足一下两个特性，则可以将复杂度从 $O(n^3)$ 优化成 $O(n^2)$ ：

区间单调性：对于任意的 $l\le l' \le r' \le r$ ，满足 $c(l',r')\le c(l,r)$
除了 $c(l',r')\le c(l,r)$ 之外，还很容易推演出如 $\le c(l',r),c(l,r')\le c(l,r)$
四边形不等式：对于任意的 $l\le l' \le r' \le r$ ，满足 $c(l,r')+c(l',r)\le c(l,r)+c(l',r')$

推论1

对于任意的 $l\le k <r$ ，以下不等式必定成立
$\le dp(l,k) + dp(k+1,r)+c(l,r)$

证明

非常直观，在上述dp的定义中， $d p (l, r)$ 是枚举所有 $k$ 计算所得的最小值，也就是说对于任意的 $k$ ， $d p (l, k) + d p (k + 1, r) + c (l, r)$ 的计算结果一定大于等于 $d p (l, r)$
且至少一个 $k$ 会使上述不等式变成等式，我们将这个 $k$ 记为 $d p (l, r)$ 的最佳决策点(optimal decistion point)，既：
$opt(l,r)\coloneqq \min \limits_{l \le k <r} \{k|dp(l,r)=dp(l,k) +dp(k+1,r)+cost(l,r)\}$
所以当 $k = o pt (l, r)$ 时，上述不等式变成等式，既
$\begin{equation} dp(l,r) = dp(l,k) + dp(k+1,r)+c(l,r) \end{equation}$

推论2

如果 $c (l, r)$ 满足区间单调性和四边形不等式，则 $d p (l, r)$ 也满足四边形不等式，既
$dp(l,r')+dp(l',r)\le dp(l,r)+dp(l',r')$
我们将这个命题定义为 $P (r)$

证明

既，需要证明命题 $P (r)$ 成立

我们对 $l\le l' \le r' \le r$ 的根据是否相等的情况分四类进行讨论，分别证明：

当 $l^{'} = l$ 时
$\begin{aligned} dp(l,r')+dp(l',r) &=dp(l,r')+dp(\textcolor{Red}{l},r) &\cdots 因为 l'=l\\ &=dp(\textcolor{Red}{l'},r')+dp(l,r) &\cdots 因为 l=l' \end{aligned}$
命题 $P (r)$ 成立，证明完成
当 $r^{'} = r$ 时
同 $l^{'} = l$ ,不赘述
当 $l^{'} = r^{'}$ 时
根据dp方程定义，当 $l^{'} = r^{'}$ 时， $d p (l^{'}, r^{'}) = 0$ ，所以下述公式成立
$\begin{equation} dp(l,r) + dp(l',r') = dp(l,r) +\textcolor{red}0=dp(l,r) \end{equation}$
设 $k = o pt (l, r)$
- 当 $r'\le k$ 时
  结合数学归纳法来证明命题 $P (r)$
  第一步：证明 $r = r^{'}$ 时， $P (r)$ 成立，上述已经证明(见 $r^{'} = r$ 的分组证明)
  第二步：证明假设 $r\ge r'$ 时 $P (r)$ 成立，可推导出 $P(\{x|x>r\})$ 成立
  由于 $r'\le k < r$ ，我们可以将第二步转化为：假设 $P (k)$ 成立，可推导出 $P (r)$ 成立。也就是说我们有如下假设：
  $dp(l,r')+dp(l',k)\le dp(l,k)+dp(l',r')$
  有了上述条件，我们可以证明：
  $\begin{aligned} dp(l,r')+dp(l',r) &\le dp(l,r') + \textcolor{Red}{dp(l',k) +dp(k+1,r)+c(l',r)} &\cdots 根据推论(1)展开 \\ &\le dp(l,r') + dp(l',k) +dp(k+1,r)+c(\textcolor{Red}l,r) &\cdots 根据c的单调性\\ &\le \textcolor{Red}{dp(l,k)+dp(l',r')}+dp(k+1,r)+c(l,r) &\cdots 根据假设\\ &=dp(l,k)+\textcolor{Red}0+dp(k+1,r)+c(l,r) &\cdots 根据dp定义\\ &=\textcolor{Red}{dp(l,r)} &\cdots 根据公式(1)\\ &=dp(l,r) + \textcolor{Red}{dp(l',r')} &\cdots 根据公式(2)\\ \end{aligned}$
  证明完毕。
- 当 $k < l^{'} = r^{'}$ 时
  同样结合数据归纳法（将命题参数的位置从 $r$ 换成 $l$ ，既命题 $P (l)$ ）
  第一步：证明 $l = l^{'}$ 时， $P (l)$ 成立，上述已经证明(见 $l^{'} = l$ 的分组证明)
  第二步，证明假设 $l\le l'$ 时 $P (l)$ 成立，可推导出 $P(\{x|x<l\})$ 也成立
  由于 $l\le k<l'$ ，也就是说 $l<k+1\le l'$ ，所以我们可以将第二步转化为：假设 $P (k + 1)$ 成立，可推导初 $P (l)$ 成立。也就是说我们有如下假设：
  $\le dp(k+1,r) + dp(l',r')$
  有了上述条件，我们可以证明：
  $\begin{aligned} dp(l,r')+dp(l',r) &\le \textcolor{Red}{ c(l,r')+dp(l,k) + dp(k+1,r')}+ dp(l',r) &\cdots 根据推论(1)展开\\ &\le c(l,\textcolor{Red}{r})+dp(l,k) + dp(k+1,r') + dp(l',r) &\cdots 根据c的单调性\\ &\le c(l,r) + dp(l,k) + \textcolor{red}{dp(k+1,r)+dp(l',r')} &\cdots 根据假设 \\ &\le c(l,r) + dp(l,k) + dp(k+1,r)+\textcolor{red}0 &\cdots 根据dp定义 \\ &= \textcolor{Red}{dp(l,r)} &\cdots 根据公式(1) \\ &= dp(l,r) + \textcolor{Red}{dp(l',r')} &\cdots 根据公式(2) \end{aligned}$
  证明完毕。
当 $l < l^{'} < r^{'} < r$ 时
设 $x = o pt (l, r), y = o pt (l^{'}, r^{'})$
由 opt 定义可得： $l\le x <r,l' \le y <r'$
- 若 $y < x$ ，将几个不等式聚合，可得 $l<l'\le y<r',x<r$ ，所以有 $l\le y < r', l' < x < r$ ，根据推论 $(1)$ 可以得到下面不等式
  $\begin{equation} \begin{aligned} dp(l,r') \le dp(l,y)+dp(y+1,r')+c(l,r')\\ dp(l',r) \le dp(l',x)+dp(x+1,r)+c(l',r) \end{aligned} \end{equation}$
  结合数据归纳法来证明命题 $P$ (这次我们将 $P$ 的参数改为 $r^{'}$ ,既命题 $P (r^{'})$ )
  第一步：证明 $r^{'} = l^{'}$ 时， $P (r^{'})$ 成立，上述已经证明(见 $l^{'} = r^{'}$ 的分组证明)
  第二步：证明假设 $r'\ge l'$ 时 $P (r^{'})$ 成立，可推导出 $P(\{x|x>r'\})$ 成立
  由于 $y\ge l'$ ，我们可以将第二步转化为：假设 $P (y)$ 成立，可推导出 $P (r^{'})$ 成立。而因为 $x > y$ ，也就是说我们有如下假设：
  $\le dp(l',y)+dp(l,x)$
  然后开始证明：
  $\begin{aligned} dp(l,r')+dp(l',r) &\le \textcolor{Red}{dp(l,y)+dp(y+1,r')+c(l,r')}+\textcolor{Red}{dp(l',x)+dp(x+1,r)+c(l',r)}&\cdots 根据公式(3)展开\\ &\le dp(l,y)+dp(y+1,r')+\textcolor{Red}{c(l',r')}+dp(l',x)+dp(x+1,r)+\textcolor{Red}{c(l,r)}&\cdots 根据c的四边形不等式\\ &\le \textcolor{Red}{dp(l',y)}+dp(y+1,r')+c(l',r')+\textcolor{Red}{dp(l,x)}+dp(x+1,r)+c(l,r)&\cdots 根据假设\\ &= \textcolor{Red}{dp(l',r') + dp(l,r)} &\cdots 根据公式(1) \end{aligned}$
  证明完毕。
- 若 $x\le y$ ，将几个不等式聚合，可得 $l\le x,l'\le y <r'<r$ ，所以有 $l\le x <r', l' \le y <r$ ，根据推论 $(1)$ 因此可得
  $\begin{equation} \begin{aligned} dp(l,r') \le dp(l,x)+dp(x+1,r')+c(l,r')\\ dp(l',r) \le dp(l',y)+dp(y+1,r)+c(l',r) \end{aligned} \end{equation}$
  再由 $x+1\le y+1 < r' < r$ 结合数据归纳法，我们可以得到如下假设
  $dp(x+1,r')+dp(y+1,r)\le dp(x+1,r)+dp(y+1,r')$
  然后开始证明：
  $\begin{aligned} dp(l,r') +dp(l',r) &\le \textcolor{Red}{dp(l,x)+dp(x+1,r')+c(l,r')}+\textcolor{Red}{dp(l',y)+dp(y+1,r)+c(l',r)} &\cdots 根据公式(4)展开\\ &\le dp(l,x)+dp(x+1,r')+\textcolor{Red}{c(l,r)}+dp(l',y)+dp(y+1,r)+\textcolor{Red}{c(l',r')} &\cdots 根据c的四边形不等式\\ &\le dp(l,x)+\textcolor{Red}{dp(x+1,r)}+c(l,r)+dp(l',y)+\textcolor{Red}{dp(y+1,r')}+c(l',r') &\cdots 根据假设\\ &= \textcolor{Red}{dp(l,r) + dp(l',r')}&\cdots 根据公式(1) \end{aligned}$
  证明完毕。

自此，四个分类都证明完毕。P为真命题

推论3

若 $d p$ 满足四边形不等式，则 $o pt$ 满足单调性，既 $opt(l,r-1)\le opt(l,r) \le opt(l+1,r)$

证明

设 $x = o pt (l, r - 1), y = o pt (l, r), z = o pt (l + 1, r)$ ，有以下不等式
$l\le x < r-1,l \le y < r, l+1 \le z < r$
我们用反证法证明：

若 $y < x$ ，结合上述不等式可得 $x+1\le r-1< r$ ，根据四边形不等式，可得
$dp(y+1,r-1)+dp(x+1,r)\le dp(y+1,r)+dp(x+1,r-1)$
根据 $y$ 是 $d p (l, r)$ 的最佳决策点，可得
$dp(l,y)+dp(y+1,r)\le dp(l,x)+dp(x+1,r)$
将两式相加去除相同相，可得
$dp(l,y)+dp(y+1,r-1)\le dp(l,x) + dp(x+1,r-1)$
这个不等式意味着对于 $d p (l, r - 1)$ 来说， $y$ 是比 $x$ 更佳的决策点，与前置条件 $x$ 是 $d p (l, r - 1)$ 的最佳决策点矛盾
因此， $x > y$ 不成立，所以 $x\le y$ 成立，既 $opt(l,r-1)\le opt(l,r)$
如 z < y，结合上述不等式，可得 $l<l+1\le z<y$ ，根据四边形不等式，可得
$dp(l,z)+dp(l+1,y)\le dp(l,y)+dp(l+1,z)$
根据 $z$ 是 $d p (l + 1, r)$ 的最佳决策点，可得
$dp(l+1,z)+dp(z+1,r)\le dp(l+1,y)+dp(y+1,r)$
两式相加去除相同项，可得
$dp(l,z)+dp(z+1,r)\le dp(l,y)+dp(y+1,r)$
这个不等式意味着对于 $d p (l, r)$ 来说， $z$ 是比 $y$ 更佳的决策点，与前置条件 $y$ 是 $d p (l, r)$ 的最佳决策点矛盾
因此， $y > z$ 不成立，所以 $\le z$ 成立，既 $opt(l,r)\le opt(l+1,r)$
证明完毕

DP优化策略

根据定理 $(3)$ ，我们可以知道 $d p$ 的最佳决策点符合 $opt(l,r-1)\le opt(l,r) \le opt(l+1,r)$ ，意味着当我们寻找 $o pt (l, r)$ 时，不用从 $[l, r]$ 中找，只需要在 $[o pt (l, r - 1), o pt (l + 1, r)]$ 的范围中找就行了
所以在实现DP时，我们可以先从 $r - l$ 小的区间开始DP，然后记录 $o pt [l, r]$ ，当 $r - l$ 变大时，它所依赖的 $o pt (l, r - 1), o pt (l + 1, r)$ 一定已经被计算出来

复杂度

整体决策的复杂度就是每个 $d p$ 状态所需要转移的复杂度，原本是
$O(\sum_{1\le l < r \le n}(r-l+1))$
经过优化后是
$\begin{aligned} &\ \ \ \ \ O(\sum_{1\le l < r \le n}(opt(l+1,r)-opt(l,r-1)+1))\\ &=O(\sum_{len=2}^n \sum_{i=1}^{n-len+1}(opt(i+1,i+len-1)-opt(i,i+len-2)+1)),len=r-l+1,i=l\\ &=O(\sum_{len=2}^n(n-len+1+opt(n-len+2,n)-opt(1,len-1)))\\ &\le O(\sum_{len=2}^n[2*n-l]) \\ &=O(n^2) \end{aligned}$

代码

for (int len = 2; len <= n; len++) { // 枚举长度
  for (int l = 1, r = len; r <= n; l++, r++) { // 枚举长度为 len 的所有区间
    dp[l][r] = INFINITY;
    for (int k = opt[l][r-1]; k <= opt[l+1][r]; k++) { // 枚举决策点
      if (dp[l][r] > dp[l][k] + dp[k+1][r] + cost(l,r)) {
        dp[l][r] = dp[l][k] + dp[k+1][r] + cost(l,r);
        opt[l][r] = k; // 更新最佳决策点
      }
    }
  }
}

参考资料

[1] 香港科技大学课件：The Knuth-Yao Quadrangle Inequality Speedup is a Consequence
of Total Monotonicity
[2] OI-wiki：四边形不等式优化
[3] cp-algorithms：Kunth’s optimization
[4] 动态规划加速原理之四边形不等式 —— 华中师大附中赵爽（这个没找到原文，随便找了个pdf，如有人知晓请告知）

本文链接：https://blog.csdn.net/notonlysuccess/article/details/130844876