dp优化

学哥 · 2018-04-04 22:30:41 · 个人记录

最近一直在搞dp的优化，心血来潮就想写一写

首先最简单的优化

前缀和优化

可以说这个优化相当不数学，只需敏锐观察，就可以了。 大概可以将O(n^t)降到O(n^{t-1}),但常数扩大

矩阵优化

一般也比较简单。但你做过通过一系列数学变化加上敏锐观察，矩阵本身计算可以将常数t^3降为 1 的题吗？

这种优化应用常见，但也只能应用到一些递推型的dp方程，对于一些复杂的，涉及到取min与max的dp，这个就用不上了

决策单调性优化

这个分为很多种，应用最广也最灵活，也最难，也最数学

一般初级的，有四边形不等式。

四边形不等式很基础，也很好用。一般，形如w[i][j]+w[i+1][j+1]\leq w[i][j+1]+w[i+1][j],i<j的都叫做满足四边形不等式。 满足此不等式等价与满足凸完全单调性。值得注意的是，不等式也可以把\leq换成\geq，此时，dp方程取max而不是min

如何一眼看出?有下例几种推论。

1. 一般前缀和类型都满足。比如说w[i][j]表示成一些关于前缀和的式子(不带乘法，开根等，只带加减)。值得注意的是，当w[i][j]+w[i+1][j+1]= w[i+1][j]+w[i][j+1]时，同样视为满足该不等式.
2. 一般的，若w[i][j]满足了,w[i][j]为前缀和形式记p[i][j]=w[i][j]*w[i][j] p[i][j]也满足，前提是为前缀和形式
3. 上述的p[i][j]可以等于两个不同但与w[i][j]类似的式子(考场最好证一下)
4. 最后还可以打表证一下

应用上述不等式，首先是证w[i][j]也就是权函数满足

然后有两种应用，

• 区间二维dp。始祖是合并石子。对于权函数取min与max没有多大关系，本人证明同样满足决策单调性.以下是长长的证明。

• 首先明确，权函数已经满足凸不等式.

• 第一大类 f[i][j]=min_{k>i}^{k<j}(f[i][k]+f[k+1][j]+w[i][j]) 这里证明需用到数学归纳法，即证明[l,r]满足一个性质，只需要证明在他范围内比它小的一个子区间满足，那么这个性质合法。设k_1是f[i+1][j]的最优解，k_2是f[i][j+1]的最优解,先假设k_1\leq k_2

  f[i][j]=f[i][k_1]+f[k_1+1][j]+w[i][j]$$ $$ f[i+1][j+1]=f[i+1][k_2]+f[k_2+1][j+1]+w[i+1][j+1]

  要证f[i][k_1]+f[k_1+1][j]+w[i][j]+f[i+1][k_2]+f[k_2+1][j+1]+w[i+1][j+1]\leq f[i+1][k_1]+f[k_1+1][j]+w[i+1][j]+f[i][k_2]+f[k_2+1][j+1]+w[i][j+1] 可以看出有一部分已经满足四边形不等式，所以接下来 只要证f[i][k_1]+f[k_1+1][j]+f[i+1][k_2]+f[k_2+1][j+1]\leq f[i+1][k_1]+f[k_1+1][j]+f[i][k_2]+f[k_2+1][j+1] 分别约掉两边对应相同的部分，得：

  f[i][k_1]+f[i+1][k_2]\leq f[i+1][k_1]+f[i][k_2]

  所以，根据数学归纳法，得证.

• 当k_2 \leq k_1时，只要把k_2 作为f[i][j]的决策点，k_1 作为f[i+1][j+1]的决策点，用同样的方法，得证(记得取max的时候，是反过来的)

• 最后，当这个证明完毕后，就可以证明其决策的单调性;设s[i][j]表示f[i][j]的最优决策 。其会有一个这样的性质 s[i][j-1]\leq s[i][j] \leq s[i+1][j] 开始证明 设 x=s[i][j-1],y<x,然后先假设成立

  f[i][j]-f[i][j]\geq f[i][j-1]-f[i][j-1] \geq 0 f[i][y]+f[y+1][j]-f[i][x]-f[x+1][j]\geq f[i][y]+f[y+1][j-1]-f[i][x]-f[x+1][j-1]\geq 0 f[y+1][j]-f[x+1][j]\geq f[y+1][j-1]-f[x+1][j-1]\geq 0 f[y+1][j]+f[x+1][j-1]\geq f[y+1][j-1]+f[x+1][j]

  因为y<x易证

• 如果是取max,看看会有什么发现。由于对dp方程与权函数的凸性证明完全只与权函数的凸性有关，暂时先不考虑取\leq \geq的问题若具有同样的单调性

  f[i][y]+f[y+1][j]-f[i][x]-f[x+1][j]\leq f[i][y]+f[y+1][j-1]=f[i][x]-f[x+1][j-1]\leq 0 f[y+1][j]+f[x+1][j-1]\leq f[y+1][j-1]+f[x+1][j]\leq 0

  也就是说，只要把不等式的符号反过来就行。这一个显然容易做到，因为dp方程的符号只与权函数有关，权函数既满足取\leq 又满足\geq。

• 同时，这也启发我们，该不等式不一定是\leq,要是情况而定，否则就会误判

以上讲述的只是区间dp的优化,更多更广的，是一类形如f[i]=max f[j]+w[i][j]的优化

一样的，先是证明w[i][j]满足该不等式，然后再巧妙证明其决策单调性。证明方法因题而异

但主要思路如下

1. 首先是判断单调性是递减还是递增。一般来说，如果i是从小到大枚举的，那么会是递增。这个单调性的意思是如果i<j,f[i]的最优决策k_1会\leq f[j]的最优决策k_2,函数图像自行脑补
2. 判断完了后依旧反证。

证出来了之后呢，把之前讲的函数图像另一种角度看，你会发现，每一个决策后对应一段区间，这个时候，优化显然。具体来说就是维护一个队列，队首始终为当前最优决策，如果队首已经不是最优，那么就把它弹掉。 对于当前枚举到的i对它决策完后，立马把它作为一个新的决策加入该队列。具体来说就是对于每个决策S来说，都有一个区间[l,r] 意思是f[l]到f[r]的最优决策都是S，但如果当前在加入i时发现，队尾决策S对应的l在把i当作决策点s时更优，显然,S丧失了作用，最后再与队尾决策二分找出加入决策i的最优决策范围

可以发现，由于随后需要二分找范围