动态规划之平行四边形优化

推荐阅读:区间dp – 石子归并

Introduction

在上篇文章中,我们详细分析了区间dp的模板与思路。其中比较关键的一点在于其状态转移方程

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w(i, j)) (i<=k<j)

其中w函数代表dp[i][k]dp[k+1][j]这两个区间合并的代价cost。

其模板代码如下:

for(int i=1; i<=n; i++){
      dp[i][i]=初始值
}

for (int len = 2; len <= n; len++) { // len代表区间中一共有几个点
  	for (int i = 1; i <= n; i++) { // 枚举起点
    		int j = i + len - 1; // 计算终点
    		if (j > n) continue;
    		for (int k = i; k < j; k++) { // 枚举分割点,构造状态转移方程
      		dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
    		}
  	}
}

容易得知,上述模板代码的时间复杂度为O(n3)

Definition

平行四边形优化是一种针对动态规划能将O(n3)的时间复杂度优化到O(n2)的方法。

能将原本的状态转移方程:

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w(i, j)) (i<=k<j)

优化成:

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w(i, j)) (s[i,j-1]≤k≤s[i+1,j])

其中s(i, j)为函数dp(i,j)对应的使得dp(i,j)取得最小值的k值。

Certification

在动态规划中,经常遇到形如下式的状态转移方程:

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)(min也可以改为max)

上述的m(i,j)表示区间[i,j]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。

下面我们通过四边形不等式来优化上述方程,首先介绍什么是”区间包含的单调性“和”四边形不等式“

(1)区间包含的单调性:如果对于i≤i'<j≤j’,有w(i’,j)≤w(i,j’),那么说明w具有区间包含的单调性。(可以形象理解为如果小区间包含于大区间中,那么小区间的w值不超过大区间的w值)

(2)四边形不等式:如果对于i≤i'<j≤j’,有w(i,j)+w(i’,j’)≤w(i’,j)+w(i,j’),我们称函数w满足四边形不等式。(可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和)

下面给出两个定理

定理一:如果上述的w函数同时满足区间包含单调性和四边形不等式性质,那么函数m也满足四边形不等式性质。

我们再定义s(i,j)表示m(i,j)取得最优值时对应的下标(即i≤k≤j时,k处的w值最大,则s(i,j)=k)。此时有如下定理

定理二:假如m(i,j)满足四边形不等式,那么s(i,j)单调,即s(i,j)≤s(i,j+1)≤s(i+1,j+1)。


总而言之,平行四边形优化就是缩小k的取值范围,将最内层的对于k的循环次数减少,从而达到降低时间复杂度的效果。在优化后的代码如下:

//n是区间长度,dp[i][j]存从i 到 j 区间合并的最优值
//w[i][j]表示从i 到 j的花费, s[i][j]记录从i 到 j的最优分割点
for(i = 1;i <= n;i++){
    dp[i][i] = 初始值;
    s[i][i] = i;
}
for(len = 2;len <= n;len++){//len选择区间长度
    for(i = 1;i <= n;i++){//枚举起点
        j = i + len - 1;//合并终点
        if(j > n)break;//不可越界
        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的循环。

优化前:

i和k组合而成总共会计算的次数是一个类似1+2+3+…的表达式,最后是O(n2)的时间复杂度

优化后:

假设求s[i, i+L]为例。

i=1时,k的取值范围为s[1][len] ~ s[2][len+1],因此循环s[2][len+1] - s[1, len]次。

i=2时,循环s[3][len+2] - s[2, L+1]次。

将上述次数相加,计算总次数:

(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]≤n

发现时间复杂度是O(n)。

Reference

百度百科

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号