http://blog.csdn.net/find_my_dream/article/details/4931222
http://blog.csdn.net/shiwei408/article/details/8791011
http://wenku.baidu.com/link?url=2DZtWmnoqlj73G2HxRUSXw840lyK5Z-GT1JgP07f_7OAuIxMFqUxT05d_9OaFBtAMkqC3RdXnZb9hI4Fb0TMQOmmTbUWNxx7F1j5G38keFW
http://blog.csdn.net/shiwei408/article/details/8791011
在动态规划的转移方程中,常见这样一种转移方程:
四边形不等式优化动态规划原理:
1.当决策代价函数w[i][j]满足w[i][j]+w[i’][j’]<=w[I;][j]+w[i][j’](i<=i’<=j<=j’)时,称w满足四边形不等式.当函数w[i][j]满足w[i’][j]<=w[i][j’] i<=i’<=j<=j’)时,称w关于区间包含关系单调.
2.如果状态转移方程m为且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.令:
s[i][j]=max{k | ma[i][j] = m[i][k-1] + m[k][j] + w[i][j]}
由于决策s具有单调性,因此状态转移方程可修改为:
证明过程: (转载)
设m[i,j]表示动态规划的状态量。
m[i,j]有类似如下的状态转移方程:
m[i,j]=opt{m[i,k]+m[k,j]}(i≤k≤j)
如果对于任意的a≤b≤c≤d,有m[a,c]+m[b,d]≤m[a,d]+m[b,c],那么m[i,j]满足四边形不等式。
以上是适用这种优化方法的必要条件
对于一道具体的题目,我们首先要证明它满足这个条件,一般来说用数学归纳法证明,根据题目的不同而不同。
通常的动态规划的复杂度是O(n3),我们可以优化到O(n2)
设s[i,j]为m[i,j]的决策量,即m[i,j]=m[i,s[i,j]]+m[s[i,j]+j]
我们可以证明,s[i,j-1]≤s[i,j]≤s[i+1,j] (证明过程见下)
那么改变状态转移方程为:
m[i,j]=opt{m[i,k]+m[k,j]} (s[i,j-1]≤k≤s[i+1,j])
复杂度分析:不难看出,复杂度决定于s的值,以求m[i,i+L]为例,
(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(n2)
对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明:
设mk[i,j]=m[i,k]+m[k,j],s[i,j]=d
对于任意k<d,有mk[i,j]≥md[i,j](这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似),接下来只要证明mk[i+1,j]≥md[i+1,j],那么只有当s[i+1,j]≥s[i,j]时才有可能有ms[i+1,j][i+1,j]≤md[i+1,j]
(mk[i+1,j]-md[i+1,j]) - (mk[i,j]-md[i,j])
=(mk[i+1,j]+md[i,j]) - (md[i+1,j]+mk[i,j])
=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) - (m[i+1,d]+m[d,j]+m[i,k]+m[k,j])
=(m[i+1,k]+m[i,d]) - (m[i+1,d]+m[i,k])
∵m满足四边形不等式,∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]
∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0
∴s[i,j]≤s[i+1,j],同理可证s[i,j-1]≤s[i,j]
证毕
http://blog.csdn.net/regina8023/article/details/44241817
四边形不等式优化的大致流程是:
如果w[i][j]满足四边形不等式即w[i][j]+w[i'][j']<=w[i][j']+w[i'][j] (i<=i'<=j<=j'),
那么f[i][j]也满足四边形不等式,
设f[i][j]=f[i-1][k]+w[k+1][j],f[i][j]在k的时候取到最优值,记s[i][j]=k,则s[i][j]满足单调性:
s[i-1][j]<=s[i][j]<=s[i][j+1]
于是k就不需要从1开始枚举了,从s[i-1][j]到s[i][j+1]枚举即可。
这里有详细证明。
一般证明dp方程满足四边形不等式比较复杂,因此我们只要把s[i][j]暴力求出,看是否满足s[i-1][j]<=s[i][j]<=s[i][j+1]即可。
http://wenku.baidu.com/link?url=2DZtWmnoqlj73G2HxRUSXw840lyK5Z-GT1JgP07f_7OAuIxMFqUxT05d_9OaFBtAMkqC3RdXnZb9hI4Fb0TMQOmmTbUWNxx7F1j5G38keFW