快速理解算法 │四边形不等式的优化
01、理论背景
四边形不等式(quadrangle inequality)应用于DP优化,是一个古老的知识点。它起源于Knuth(高纳德)1971年的一篇论文,用来解决最优二叉搜索树问题。1980年,储枫(F. Frances Yao,姚期智的夫人)做了深入研究,扩展为一般性的DP优化方法,把一些复杂度O(n3)的DP问题,优化为O(n2)。所以这个方法又被称为“Knuth-Yao DP Speedup Theorem”。
02、应用场合
有一些常见的DP问题,通常是区间DP问题,它的状态转移方程是:
d p [ i ] [ j ] = m i n ( d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + w [ i ] [ j ] )
其中i < = k < j ,初始值d p [ i ] [ i ] 已知。m i n ( ) 也可以是m a x ( ) ,见本篇第6小节的说明。
方程的含义是:
(1)d p [ i ] [ j ] 表示从i 状态到j 状态的最小花费。题目一般是求d p [ 1 ] [ n ] ,即从起始点1 到终点n 的最小花费。
(2)d p [ i ] [ k ] + d p [ k + 1 ] [ j ]体现了递推关系。k 在i 和j 之间滑动,k 有一个最优值,使得d p [ i ] [ j ] 最小。
(3)w [ i ] [ j ]的性质非常重要。w [ i ] [ j ] 是和题目有关的费用,如果它满足四边形不等式和单调性,那么用DP计算dp的时候,就能进行四边形不等式优化。
这类问题的经典的例子是“石子合并”,它的转移矩阵就是上面的d p [ i ] [ j ] ,w [ i ] [ j ] 是从第i 堆石子到第j 堆石子的总数量。
石子合并
题目描述:
有n堆石子排成一排,每堆石子有一定的数量。将n堆石子并成为一堆。每次只能合并相邻的两堆石子,合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆,求总的最小花费。
输入:测试数据第一行是整数n,表示有n堆石子。接下来的一行有n个数,分别表示这n堆石子的数目。
输出:总的最小花费。
输入样例:
3
2 4 5
输出样例:
17
提示:样例的计算过程是:第一次合并2+4=6;第二次合并6+5=11;总花费6+11=17。
在阅读后面的讲解时,读者可以对照“石子合并”这个例子来理解。注意,石子合并有多种情况和解法,详情见本文的例题“洛谷P1880石子合并”。
d p [ i ] [ j ] 是一个转移矩阵,如何编码填写这个矩阵?复杂度是多少?如果直接写i 、 j 、 k 的3层循环,复杂度O(n3)。
注意3层循环的写法。d p [ i ] [ j ]是大区间,它从小区间d p [ i ] [ k ] 和d p [ k + 1 ] [ j ] 转移而来,所以应该先计算小区间,再逐步扩展到大区间。
for(int i=1; i<=n; i++)
dp[i][i] = 0; //初始值
for(int len = 2; len <= n; len++) //len:从小区间扩展到大区间
for(int i = 1; i <= n-len+1; i++){ // 区间起点i
int j = i + len - 1; // 区间终点j
for(int k = i; k < j; k++) //大区间[i,j]从小区间[i,k]和[k+1,j]转移而来
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
03、四边形不等式优化
只需一个简单的优化操作,就能把上面代码的复杂度变为O(n2)。这个操作就是把循环i ≤ k < j 改为:
s [ i ] [ j − 1 ] ≤ k ≤ s [ i + 1 ] [ j ]
其中s [ i ] [ j ] 记录从i到j的最优分割点。在计算d p [ i ] [ j ] 的最小值时得到区间[ i , j ] 的分割点k ,记录在s [ i ] [ j ]中,用于下一次循环。
这个优化被称为四边形不等式优化。下面给出优化后的代码,优化见注释的几行代码。
for(i = 1;i <= n;i++){
dp[i][i] = 0;
s[i][i] = i; //s[][]的初始值
}
for(int len = 2; len <= n; len++)
for(int i = 1; i <= n-len+1; i++){
int j = i + len - 1;
for(k = s[i][j - 1]; k <= s[i + 1][j]; k++){ //缩小循环范围
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + w[i][j]){ //是否更优
dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j];
s[i][j] = k; //更新最佳分割点
}
}
}
代码的复杂度是多少?
代码中i 和k 这2个循环,优化前是O(n2)的。优化后,每个i 内部的k 的循环次数是s [ i + 1 ] [ j ] − s [ i ] [ j − 1 ] ,其中j = i + l e n − 1 。那么:
i = 1 时,k 循环s [ 2 ] [ l e n ] − s [ 1 ] [ l e n − 1 ]次。
i = 2 时,k 循环s [ 3 ] [ l e n + 1 ] − s [ 2 ] [ l e n ] 次。
…
i = n − l e n + 1 时,k 循环s [ n − l e n + 2 ] [ n ] − s [ n − l e n + 1 ] [ n + 1 ] 次。
上述次数相加,总次数:
s [ 2 ] [ l e n ] − s [ 1 , l e n − 1 ] + s [ 3 ] [ l e n + 1 ] − s [ 2 , l e n ] + … + s [ n + 1 , n ] − s [ n ] [ n ]
= s [ n − l e n + 2 ] [ n ] − s [ 1 ] [ l e n − 1 ]
< n
i 和k 循环的时间复杂度优化到了O(n)。总复杂度从O(n3)优化到了O(n2)。
在后面的四边形不等式定理证明中,将更严谨地证明复杂度。
下图给出了四边形不等式优化的效果,s1是区间[ i , j − 1 ] 最优分割点,s2是区间[ i + 1 , j ] 的最优分割点。
▍图1 四边形不等式优化效果
读者对代码可能有2个疑问:
(1)为什么能够把i < = k < j缩小到s [ i ] [ j − 1 ] ≤ k ≤ s [ i + 1 ] [ j ] ?
(2)s [ i ] [ j − 1 ] ≤ s [ i + 1 ] [ j ] 成立吗?
下面几节给出四边形不等式优化的正确性和复杂度的严谨证明,解答了这2个问题。
04、四边形不等式定义和单调性定义
在四边形不等式DP优化中,对于w ,有2个关键内容:四边形不等式定义、单调性。
(1)四边形不等式定义:设w 是定义在整数集合上的二元函数,对于任意整数i ≤ i ′ ≤ j ≤ j ′ ,如果有 w ( i , j ) + w ( i ′ , j ′ ) ≤ w ( i , j ′ ) + w ( i ′ , j ) ,则称w 满足四边形不等式。
四边形不等式可以概况为:两个交错区间的w 和,小于等于小区间与大区间的w 和。
为什么被称为“四边形”?把它变成一个几何图,画成平行四边形,见下面图中的四边形i ′ i j j ′ 。图中对角线长度和i j + i ′ j ′ 大于平行线长度和i j ′ + i ′ j ,这与四边形的性质是相反的,所以可以理解成“反四边形不等式”。请大家注意,这个“四边形”只是一个帮助理解的示意图,并没有严谨的意义。也有其他的四边形画法,下面这种四边形是储枫论文中的画法。当中间两个点i ′ = j 时,四边形变成了一个三角形。
▍图2 四边形不等式 w(i, j) + w(i', j') ≤ w(i, j') + w(i', j)
定义1的特例是定义2。
(2)四边形不等式定义2:对于整数i < i + 1 ≤ j < j + 1 ,如果有 w ( i , j ) + w ( i + 1 , j + 1 ) ≤ w ( i , j + 1 ) + w ( i + 1 , j ) ,称w 满足四边形不等式。
定义1和定义2实际上是等价的,它们可以互相推导。
(3)单调性:设w是定义在整数集合上的二元函数,如果对任意整数i ≤ i ′ ≤ j ≤ j ′ ,有w ( i , j ′ ) ≥ w ( i ′ , j ) ,称w具有单调性。
单调性可以形象地理解为,如果大区间包含小区间,那么大区间的w 值超过小区间的w 值。
▍图3 w的单调性w(i, j') ≥ w(i', j)
在石子合并问题中,令wi等于从第i堆石子加到第j堆石子的石子总数。它满足四边形不等式的定义、单调性:
w [ i ] [ j ′ ] ≥ w [ i ′ ] [ j ] ,满足单调性;
w [ i ] [ j ] + w [ i ′ ] [ j ′ ] = w [ i ] [ j ′ ] + w [ i ′ ] [ j ] ,满足四边形不等式定义。
利用w 的四边形不等式、单调性的性质,可以推导出四边形不等式定理,用于DP优化。
05、四边形不等式定理(Knuth-Yao DP Speedup Theorem)
在储枫的论文中,提出并证明了四边形不等式定理。
四边形不等式定理:如果w ( i , j ) 满足四边形不等式和单调性,则用DP计算d p [ ] [ ] 的时间复杂度是O(n2)的。
这个定理是通过下面2个更详细的引理来证明的。
引理1:状态转移方程 d p [ i ] [ j ] = m i n ( d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + w [ i ] [ j ] ) ,如果w [ i ] [ j ] 满足四边形不等式和单调性,那么d p [ i ] [ j ] 也满足四边形不等式。
引理2:记s [ i ] [ j ] = k 是d p [ i ] [ j ] 取得最优值时的k ,如果d p 满足四边形不等式,那么有s [ i ] [ j − 1 ] ≤ s [ i ] [ j ] ≤ s [ i + 1 ] [ j ] ,即s [ i ] [ j − 1 ] ≤ k ≤ s [ i + 1 ] [ j ] 。
定理2直接用于DP优化,复杂度O(n2)。
06
证明四边形不等式定理
这里翻译储枫论文中对引理1和引理2的证明,并加上了本作者的一些说明。
定义方程c ( i , j ) :
c ( i , i ) = 0
c ( i , j ) = w ( i , j ) + m i n ( c ( i , k − 1 ) + c ( k , j ) ) i < k ≤ j (6−1)
前面的例子d p [ i ] [ j ] 和这里的c ( i , j ) 略有不同,d p [ i ] [ j ] = m i n ( d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + w [ i ] [ j ] ) ,其中w [ i ] [ j ] 在min()内部。证明过程是一样的。
公式(6-1)的w 要求满足四边形不等式:
w ( i , j ) + w ( i ′ , j ′ ) ≤ w ( i ′ , j ) + w ( i , j ′ ) i ≤ i ′ ≤ j ≤ j ′ (6 −2)
而且要求w 是单调的:w ( i ′ , j ) ≤ w ( i , j ′ )
[ i ′ , j ] ⊆ [ i , j ′ ]
- 证明引理1
引理1:如果w ( i , j ) 满足四边形不等式和单调性,那么c ( i , j ) 也满足四边形不等式:
c ( i , j ) + c ( i ′ , j ′ ) ≤ c ( i ′ , j ) + c ( i , j ′ ) i ≤ i ′ ≤ j ≤ j ′ (6−3)
下面证明(6-3)。
当i = i ′ 或j = j ′时(6-3)显然成立,下面考虑另外2个情况:A). i < i ′ = j < j ′ 和B).i < i ′ < j < j ′ 。
case A). i < i’ = j < j’
代入公式(6-3),得到一个“反”三角形不等式(图4的三角形i j j ′,两边的和小于第三边):
c ( i , j ) + c ( j , j ′ ) ≤ c ( i , j ′ ) i < j < j ′ (6−4)
现在证明公式(6-4)。
假设c ( i , j ′ ) 在k = z 处有最小值,即c ( i , j ′ ) = c z ( i , j ′ ) 。这里定义c k ( i , j ) 等于w ( i , j ) + c ( i , k − 1 ) + c ( k , j ) 。
有2个对称情况A1)和A2)。
case A1). z ≤ j
z 是( i , j ′ ) 区间的最优点,不是( i , j ) 区间的最优点,所以有:
c ( i , j ) ≤ cz ( i , j ) = w ( i , j ) + c ( i , z − 1 ) + c ( z , j )
在两边加上c ( j , j ′ ):
c ( i , j ) + c ( j , j ′ ) ≤ w ( i , j ) + c ( i , z − 1 ) + c ( z , j ) + c ( j , j ′ )
≤ w ( i , j ′ ) + c ( i , z − 1 ) + c ( z , j ′ )
= c ( i , j ′ )
上面的推导时利用了下面2条:
1)w 的单调性,有w ( i , j ) ≤ w ( i , j ′ ) ;
2)公式(6-4)的归纳假设:假设z ≤ j ≤ j ′ 时成立,递推出i < j < j ′ 时公式(6-4)也成立。观察下面的图,有c ( z , j ) + c ( j , j ′ ) ≤ c ( z , j ′ ) ,它满足反三角形不等式。
▍图4 储枫论文图-引理1的case A1
case A2). z ≥ j 。是A1)的对称情况。
case B). i < i ′ < j < j ′
假设公式(6-3)右边的小区间c ( i ′ , j ) 和大区间c ( i , j ′ ) 分别在k = y 和k = z处有最小值,记为:
c ( i ′ , j ) = c y ( i ′ , j )
c ( i , j ′ ) = c z ( i , j ′ )
同样有2个对称情况B1)和B2)。
case B1). z ≤ y
有 c ( i ′ , j ′ ) ≤ c y ( i ′ , j ′ )
和 c ( i , j ) ≤ c z ( i , j )
两式相加得:
c ( i , j ) + c ( i ′ , j ′ )
≤ c z ( i , j ) + c y ( i ′ , j ′ )
= w ( i , j ) + w ( i ′ , j ′ ) + c ( i , z − 1 ) + c ( z , j ) + c ( i ′ , y − 1 ) + c ( y , j ′ ) (6 −5)
公式(6-5)的进一步推导利用了下面2条:
1)根据w 的四边形不等式,有w ( i , j ) + w ( i ′ , j ′ ) ≤ w ( i ′ , j ) + w ( i , j ′ ) ;
2)根据公式(6-3)的归纳假设,即假设z ≤ y < j < j ′ 时成立。观察下图,有c ( z , j ) + c ( y , j ′ ) ≤ c ( y , j ) + c ( z , j ′ ) ,满足反四边形不等式。
▍图5 储枫论文图-引理1的case B1
则公式(6-5)变为:
c ( i , j ) + c ( i ′ , j ′ )
≤ w ( i ′ , j ) + w ( i , j ′ ) + c ( i , z − 1 ) + c ( i ′ , y − 1 ) + c ( y , j ) + c ( z , j ′ )
≤ c y ( i ′ , j ) + c z ( i , j ′ )
= c ( i ′ , j ) + c ( i , j ′ )
case B2). z ≥ y 。是B1)的对称情况。
引理1证毕。
- 证明引理2
用K c ( i , j )表示m a x { k ∣ c k ( i , j ) = c ( i , j ) } ,也就是使c ( i , j ) 得到最小值的那些k 中,最大的那个是K c ( i , j ) 。定义K c ( i , i ) = i 。K c ( i , j ) 就是前面例子中的s [ i ] [ j ] 。
引理2:K c ( i , j ) ≤ K c ( i , j + 1 ) ≤ K c ( i + 1 , j + 1 ) (6−6)
下面是证明。
i = j时显然成立,下面假设i < j 。
先证明公式(6-6)的第一部分K c ( i , j ) ≤ K c ( i , j + 1 ) 。这等价于证明:对于i < k ≤ k ′ ≤ j ,有
c k ′ ( i , j ) ≤ c k ( i , j ) ⇒ c k ′ ( i , j + 1 ) ≤ c k ( i , j + 1 ) (6−7)
公式(6-7)的意思是:如果c k ′ ( i , j ) ≤ c k ( i , j ) 成立,那么c k ′ ( i , j + 1 ) ≤ c k ( i , j + 1 ) 也成立。c k ′ ( i , j ) ≤ c k ( i , j )的含义是,在[ i , j ] 区间,k ′ 是比k 更好的分割点,可以把k ′ 看成[ i , j ] 的最优分割点。扩展到区间[ i , j + 1 ] 时,有c k ′ ( i , j + 1 ) ≤ c k ( i , j + 1 ) ,即k仍然是比k 更好的分割点。也就是说,区间[ i , j + 1 ] 的最优分割点肯定大于等于k ′ 。
下面证明公式(6-7)。
根据四边形不等式,在k ≤ k ′ ≤ j < j + 1 时,有
c ( k , j ) + c ( k ′ , j + 1 ) ≤ c ( k ′ , j ) + c ( k , j + 1 )
在两边加上 w ( i , j ) + w ( i , j + 1 ) + c ( i , k − 1 ) + c ( i , k ′ − 1 ) ,得:
c k ( i , j ) + c k ′ ( i , j + 1 ) ≤ c k ′ ( i , j ) + c k ( i , j + 1 )
把 ck(i, j) 移到右边:
c k ′ ( i , j + 1 ) ≤ c k ′ ( i , j ) + c k ( i , j + 1 ) − c k ( i , j ) ( 6 − 8 )
把(6-7)的c k ′ ( i , j ) ≤ c k ( i , j ) 的两边加上c k ( i , j + 1 ) :
c k ′ ( i , j ) + c k ( i , j + 1 ) ≤ c k ( i , j ) + c k ( i , j + 1 )
c k ′ ( i , j ) + c k ( i , j + 1 ) − c k ( i , j ) ≤ c k ( i , j + 1 )
结合(6-8),得c k ′ ( i , j + 1 ) ≤ c k ( i , j + 1 ) ,公式(6-7)成立。
同样可以证明,公式(6-6)的右半部分K c ( i , j + 1 ) ≤ K c ( i + 1 , j + 1 ) ,在i < i + 1 ≤ k ≤ k ′ 时成立。
引理2说明当i、j增大时,K c ( i , j ) 是非递减的。
- 证明四边形不等式定理
利用引理2,可推论出四边形不等式定理,即用DP计算所有的c ( i , j ) 的时间复杂度是O(n2)的。下面对这一结论进行说明。
用DP计算c ( i , j )时,是按δ = j − i = 0 , 1 , 2 , . . . , n − 1 的间距逐步增加进行递推计算的。具体过程请回顾前面第2节求dpi的代码。从c ( i , j )递推到c ( i , j + 1 ) 时,只需要K c ( i + 1 , j + 1 ) − K c ( i , j ) 次最少限度的操作就够了。总次数是多少呢?对一个固定的δ ,计算所有的c ( i , j ) , 1 ≤ i ≤ n − δ , j = i + δ ,次数是:
i = 1时:K c ( 1 + 1 , 1 + δ + 1 ) − K c ( 1 , δ + 1 ) = K c ( 2 , δ + 2 ) − K c ( 1 , δ + 1 )
i = 2时:K c ( 2 + 1 , 2 + δ + 1 ) − K c ( 2 , δ + 2 ) = K c ( 3 , δ + 3 ) − K c ( 2 , δ + 2 )
i = 3时:K c ( 3 + 1 , 3 + δ + 1 ) − K c ( 3 , δ + 3 ) = K c ( 4 , δ + 4 ) − K c ( 3 , δ + 3 )
…
i = n − δ 时:K c ( n − δ + 1 , n − δ + δ + 1 ) − K c ( n − δ , δ + n − δ ) = K c ( n − δ + 1 , n + 1 ) − K c ( n − δ , n )
以上式子相加,次数 = K c ( n − δ + 1 , n + 1 ) − K c ( 1 , δ + 1 ) ,小于n 。
对一个δ ,计算次数是O ( n ) 的;有n 个δ ,总计算复杂度是O ( n 2 )的。
以上证明了四边形不等式定理。
- min和max
前面讨论的都是min,如果是max,也可以进行四边形不等式优化。此时四边形不等式是“反”的:
w ( i , j ) + w ( i ′ , j ′ ) ≥ w ( i ′ , j ) + w ( i , j ′ ) i ≤ i ′ ≤ j ≤ j ′
定义:
c ( i , j ) = w ( i , j ) + m a x ( a ( i , k ) + b ( k , j ) ) i ≤ k ≤ j
引理3:若w、a、b都满足反四边形不等式,那么c cc也满足反四边形不等式。
引理4:如果a 和b 满足反四边形不等式,那么:
K c ( i , j ) ≤ K c ( i , j + 1 ) ≤ K c ( i + 1 , j + 1 )
i ≤ j
证明与引理1和引理2的证明类似。
07、一维决策单调性优化
上述的四边形不等式优化,是“二维决策单调性”优化。在“一维决策单调性”的情况下也能优化。
李煜东《算法竞赛进阶指南》“0x5B四边形不等式”指出:状态转移方程 F [ i ] = m i n 0 ≤ j < i { F [ j ] + v a l ( j , i ) } ,若v a l 满足四边形不等式,则F 具有决策单调性,可以把DP计算F [ i ] 的复杂度从O(N2)优化到O(NlogN)。
08、例题
拿到题目后,先判断w是否单调、是否满足四边形不等式,再使用四边形不等式优化DP。
- 石子合并
洛谷 P1880
https://www.luogu.com.cn/problem/P1880
题目描述:
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成1堆的最小得分和最大得分
输入:
数据的第 1 行是正整数 N,表示有 N 堆石子。
第 2 行有 N 个整数,第 i 个整数 ai表示第 i 堆石子的个数。
输出:
输出共 2 行,第 1 行为最小得分,第 2 行为最大得分。
样例输入:
4
4 5 9 4
样例输出:
43
54
题解:
(1)如果石子堆没有顺序,可以任意合并,用贪心法,每次选择最小的两堆合并。
(2)本题要求只能合并相邻的两堆,不能用贪心法。贪心操作是每次合并时找石子数相加最少的两堆相邻石子。例如环形石子堆开始是{2, 4, 7, 5, 4, 3},下面用贪心得到最小值64,但是另一种方法得到63。
(3)用四边形优化DP求解石子合并的最小值,复杂度是O(n2)。
状态转移矩阵d p [ i ] [ j ] 前文已有说明,这里不再赘述。
最小值用四边形不等式优化DP,w 在四边形不等式中取等号:w [ i ] [ j ] + w [ i ′ ] [ j ′ ] = w [ i ] [ j ′ ] + w [ i ′ ] [ j ] 。
本题的石子堆是环状的,转换为线形的更方便处理。复制和原来一样的数据,头尾接起来,使n 的数列转化为2n的数列,变成线形的。
(4)这一题除了求最小值,还求最大值。虽然最大值也用DP求解,但是它不满足反四边形不等式的单调性要求,不能优化。而且也没有必要优化,可以用简单的推理得到:区间[ i , j ] 的最大值,等于区间[ i , j − 1 ]和[ i + 1 , j ] 中的最大值加上w ( i , j ) 。
(5)石子合并问题的最优解法是GarsiaWachs算法,复杂度O(nlogn)。读者可以参考“洛谷P5569 石子合并”,这题N ≤ 40000 N ≤ 40000N≤40000,用DP会超时。
- 最优二叉搜索树
最优二叉搜索树是Knuth(高纳德)解决的经典问题,是四边形不等式优化的起源。
题目描述:
给定n 个不同元素的集合S = ( e 1 , e 2, . . . , e n ) ,有e 1 < e 2 < . . . < e n,把S 的元素建一棵二叉搜索树,希望查询频率越高的元素离根越近。
访问树中元素e i 的成本cost(ei)等于从根到该元素结点的路径边数。给定元素的查询频率f ( e 1 ) , f ( e 2 ) , . . . , f ( e n ),定义一棵树的总成本是:
f ( e 1 ) ∗ c o s t ( e 1 ) + f ( e 2 ) ∗ c o s t ( e 2 ) + . . . + f ( e n ) ∗ c o s t ( e n )
总成本最低的树就是最优二叉搜索树。
输入:
输入包含多个实例,每行一个。每行以1 ≤ n ≤ 250 开头,表示S 的大小。在n 之后,在同一行中,有n 个非负整数,它们表示元素的查询频率,0 ≤ f ( e i ) ≤ 100。
输出:
对于输入的每个实例,输出一行,打印最优二叉搜索树的总成本。
样例输入:
1 5
3 10 10 10
3 5 10 20
样例输出:
0
20
20
题解:
二叉搜索树(BST)的特点是每个结点的值,比它的左子树上所有结点的值大,比右子树上所有值小。二叉搜索树的中序遍历,是从小到大的排列。第3个样例的最优二叉搜索树的形状见下图,它的总成本是5∗2+10∗1=20。
▍图6 二叉搜索树
题目给的元素已经按照从小到大排列,可以方便地组成一棵BST。
设d p [ i ] [ j ] 是区间[ i , j ] 的元素组成的BST的最小值。把区间[ i , j ] 分成两部分[ i , k − 1 ]和[ k + 1 , j ] ,k 在i 和j 之间滑动。用区间[ i , j ]建立的二叉树,k 是根结点。这是典型的区间DP,状态转移方程:
d p [ i ] [ j ] = m i n { d p [ i ] [ k − 1 ] + d p [ k + 1 ] [ j ] + w ( i , j ) − e [ k ] }
w ( i , j )是区间和,w ( i , j ) = f i + f i + 1 + . . . + f j 。当把两棵左右子树连在根结点上时,本身的深度增加1,所以每个元素都多计算一次,这样就解决了cost(ei)的计算。最后,因为根节点k 的层数是0,所以减去根节点的值e [ k ]。
w(i, j)符合四边形不等式优化的条件,所以d p [ i ] [ j ] 可以用四边形不等式优化。
上一篇: 《小窗幽记》完整汇总(上册共计六卷)
下一篇: 整数近似函数的特性
推荐阅读
-
说说对排序算法的一些理解 - 理解排序 - 快速排序
-
如何快速编写与优化快速排序算法的代码实例
-
三步走教你轻松理解快速排序的三大优化技巧图解
-
谈一谈我对快速排序优化及递归理解的想法与探讨
-
玩转机器学习:带你理解粒子群优化(PSO)算法的基础原理(第一篇)
-
【Netty】「萌新入门」(七)ByteBuf 的性能优化-堆内存的分配和释放都是由 Java 虚拟机自动管理的,这意味着它们可以快速地被分配和释放,但是也会产生一些开销。 直接内存需要手动分配和释放,因为它由操作系统管理,这使得分配和释放的速度更快,但是也需要更多的系统资源。 另外,直接内存可以映射到本地文件中,这对于需要频繁读写文件的应用程序非常有用。 此外,直接内存还可以避免在使用 NIO 进行网络传输时发生数据拷贝的情况。在使用传统的 I/O 时,数据必须先从文件或网络中读取到堆内存中,然后再从堆内存中复制到直接缓冲区中,最后再通过 SocketChannel 发送到网络中。而使用直接缓冲区时,数据可以直接从文件或网络中读取到直接缓冲区中,并且可以直接从直接缓冲区中发送到网络中,避免了不必要的数据拷贝和内存分配。 通过 ByteBufAllocator.DEFAULT.directBuffer 方法来创建基于直接内存的 ByteBuf: ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); 通过 ByteBufAllocator.DEFAULT.heapBuffer 方法来创建基于堆内存的 ByteBuf: ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); 注意: 直接内存是一种特殊的内存分配方式,可以通过在堆外申请内存来避免 JVM 堆内存的限制,从而提高读写性能和降低 GC 压力。但是,直接内存的创建和销毁代价昂贵,因此需要慎重使用。 此外,由于直接内存不受 JVM 垃圾回收的管理,我们需要主动释放这部分内存,否则会造成内存泄漏。通常情况下,可以使用 ByteBuffer.clear 方法来释放直接内存中的数据,或者使用 ByteBuffer.cleaner 方法来手动释放直接内存空间。 测试代码: public static void testCreateByteBuf { ByteBuf buf = ByteBufAllocator.DEFAULT.buffer(16); System.out.println(buf.getClass); ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); System.out.println(heapBuf.getClass); ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); System.out.println(directBuf.getClass); } 运行结果: class io.netty.buffer.PooledUnsafeDirectByteBuf class io.netty.buffer.PooledUnsafeHeapByteBuf class io.netty.buffer.PooledUnsafeDirectByteBuf 池化技术 在 Netty 中,池化技术指的是通过对象池来重用已经创建的对象,从而避免了频繁地创建和销毁对象,这种技术可以提高系统的性能和可伸缩性。 通过设置 VM options,来决定池化功能是否开启: -Dio.netty.allocator.type={unpooled|pooled} 在 Netty 4.1 版本以后,非 Android 平台默认启用池化实现,Android 平台启用非池化实现; 这里我们使用非池化功能进行测试,依旧使用的是上面的测试代码 testCreateByteBuf,运行结果如下所示: class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeHeapByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf 可以看到,ByteBuf 类由 PooledUnsafeDirectByteBuf 变成了 UnpooledUnsafeDirectByteBuf; 在没有池化的情况下,每次使用都需要创建新的 ByteBuf 实例,这个操作会涉及到内存的分配和初始化,如果是直接内存则代价更为昂贵,而且频繁的内存分配也可能导致内存碎片问题,增加 GC 压力。 使用池化技术可以避免频繁内存分配带来的开销,并且重用池中的 ByteBuf 实例,减少了内存占用和内存碎片问题。另外,池化技术还可以采用类似 jemalloc 的内存分配算法,进一步提升分配效率。 在高并发环境下,池化技术的优点更加明显,因为内存的分配和释放都是比较耗时的操作,频繁的内存分配和释放会导致系统性能下降,甚至可能出现内存溢出的风险。使用池化技术可以将内存分配和释放的操作集中到预先分配的池中,从而有效地降低系统的内存开销和风险。 内存释放 当在 Netty 中使用 ByteBuf 来处理数据时,需要特别注意内存回收问题。 Netty 提供了不同类型的 ByteBuf 实现,包括堆内存(JVM 内存)实现 UnpooledHeapByteBuf 和堆外内存(直接内存)实现 UnpooledDirectByteBuf,以及池化技术实现的 PooledByteBuf 及其子类。 UnpooledHeapByteBuf:通过 Java 的垃圾回收机制来自动回收内存; UnpooledDirectByteBuf:由于 JVM 的垃圾回收机制无法管理这些内存,因此需要手动调用 release 方法来释放内存; PooledByteBuf:使用了池化机制,需要更复杂的规则来回收内存; 由于池化技术的特殊性质,释放 PooledByteBuf 对象所使用的内存并不是立即被回收的,而是被放入一个内存池中,待下次分配内存时再次使用。因此,释放 PooledByteBuf 对象的内存可能会延迟到后续的某个时间点。为了避免内存泄漏和占用过多内存,我们需要根据实际情况来设置池化技术的相关参数,以便及时回收内存; Netty 采用了引用计数法来控制 ByteBuf 对象的内存回收,在博文 「源码解析」ByteBuf 的引用计数机制 中将会通过解读源码的形式对 ByteBuf 的引用计数法进行深入理解; 每个 ByteBuf 对象被创建时,都会初始化为1,表示该对象的初始计数为1。 在使用 ByteBuf 对象过程中,如果当前 handler 已经使用完该对象,需要通过调用 release 方法将计数减1,当计数为0时,底层内存会被回收,该对象也就被销毁了。此时即使 ByteBuf 对象还在,其各个方法均无法正常使用。 但是,如果当前 handler 还需要继续使用该对象,可以通过调用 retain 方法将计数加1,这样即使其他 handler 已经调用了 release 方法,该对象的内存仍然不会被回收。这种机制可以有效地避免了内存泄漏和意外访问已经释放的内存的情况。 一般来说,应该尽可能地保证 retain 和 release 方法成对出现,以确保计数正确。
-
快速理解算法 │四边形不等式的优化
-
计算机视觉中,究竟有哪些好用的目标跟踪算法(下)-快速变形主要因为CF是模板类方法。容易跟丢这个比较好理解,前面分析了相关滤波是模板类方法,如果目标快速变形,那基于HOG的梯度模板肯定就跟不上了,如果快速变色,那基于CN的颜色模板肯定也就跟不上了。这个还和模型更新策略与更新速度有关,固定学习率的线性加权更新,如果学习率太大,部分或短暂遮挡和任何检测不准确,模型就会学习到背景信息,积累到一定程度模型跟着背景私奔了,一去不复返。如果学习率太小,目标已经变形了而模板还是那个模板,就会变得不认识目标。(举个例子,多年不见的同学,你很可能就认不出了,而经常见面的同学,即使变化很大你也认识,因为常见的同学在你大脑里面的模型在持续更新,而多年不见就是很久不更新) 快速运动主要是边界效应(Boundary Effets),而且边界效应产生的错误样本会造成分类器判别力不够强,下面分训练阶段和检测阶段分别讨论。 训练阶段,合成样本降低了判别能力。如果不加余弦窗,那么移位样本是长这样的: 除了那个最原始样本,其他样本都是“合成”的,100*100的图像块,只有1/10000的样本是真实的,这样的样本集根本不能拿来训练。如果加了余弦窗,由于图像边缘像素值都是0,循环移位过程中只要目标保持完整那这个样本就是合理的,只有目标中心接近边缘时,目标跨越边界的那些样本是错误的,这样虽不真实但合理的样本数量增加到了大约2/3(padding= 1),即使这样仍然有1/3(3000/10000)的样本是不合理的,这些样本会降低分类器的判别能力。再者,加余弦窗也不是“免费的”,余弦窗将图像块的边缘区域像素全部变成0,大量过滤掉分类器本来非常需要学习的背景信息,原本训练时判别器能看到的背景信息就非常有限,我们还加了个余弦窗挡住了背景,这样进一步降低了分类器的判别力(是不是上帝在我前遮住了帘。不是上帝,是余弦窗)。 检测阶段,相关滤波对快速运动的目标检测比较乏力。相关滤波训练的图像块和检测的图像块大小必须是一样的,这就是说你训练了一个100*100的滤波器,那你也只能检测100*100的区域,如果打算通过加更大的padding来扩展检测区域,那样除了扩展了复杂度,并不会有什么好处。目标运动可能是目标自身移动,或摄像机移动,按照目标在检测区域的位置分四种情况来看: 如果目标在中心附近,检测准确且成功。 如果目标移动到了边界附近但还没有出边界,加了余弦窗以后,部分目标像素会被过滤掉,这时候就没法保证这里的响应是全局最大的,而且,这时候的检测样本和训练过程中的那些不合理样本很像,所以很可能会失败。 如果目标的一部分已经移出了这个区域,而我们还要加余弦窗,很可能就过滤掉了仅存的目标像素,检测失败。 如果整个目标已经位移出了这个区域,那肯定就检测失败了。 以上就是边界效应(Boundary Effets),推荐两个主流的解决边界效应的方法,但速度比较慢,并不推荐用于实时场合。