众所周知。。dp的优化有很多种。。最主要的就是借助数据结构优化。。

这里介绍一种优化方法，比较偏门，并不借助数据结构优化，但是对于某些dp方程可以有效地降低转移复杂度。 第一次写正经的文章。。。不要喷我。。

我们先看一个方程 f[i][j]=max(f[i-k][k]) k<=min(j,i)

首先看到这个状态表示是O(N^2)的 转移是O(N)的 总复杂度O(N^3)

如何优化？我们可以线段树乱搞一下。。不过那样太麻烦了。。

我们观察相邻的两项

f[i][j]=max(f[i-k][k]+w[i]) k<=min(j,i)

f[i][j+1]=max(f[i-k][k]+w[i]) k<=min(j+1,i)

咦，好像很奇怪啊，下一项和前一项只差一个j+1啊

那么我们把j+1项稍微变形

f[i][j+1]=max(f[i][j-1],f[i-min(j,i)][min(j,i)]+w[i])

前面的f[i][j-1]已经考虑了[1,min(j-1,i)]这一段了，最后那个就是多出来的。

这个就减少了大量冗余计算。

其实这个方程并没有太大意义，而且非常特殊。。

由于我太弱了。。所以yy了这样一个方程。。。。不过一般这种优化的思路都是这个的。。

但是这种优化方法还是不太好想到的。。拿两道例题说说吧。。

 

[Usaco2009 Nov]硬币游戏

题意：

农夫约翰的奶牛喜欢玩硬币游戏，因此他发明了一种称为“Xoinc”的两人硬币游戏。

初始时，一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上，从堆顶数起的第I枚硬币的币值为C_i (1 <= C_i <= 100,000)。

开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。

在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。

当没有硬币可拿时，游戏结束。 两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？

例如：

第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币。

 

一看就是dp嘛。。 好像方程也很像我刚刚yy的呢。。。。。

很容易列出方程：

f[i][j]表示剩余i枚硬币 上一个人拿了j枚硬币时的最优解

f[i][j]=max(sum[i]-f[i-k][k]) k<=min(j*2,i)

咦 N^3过不去

这方程明明长得跟刚才那个我yy的一样。。。于是套用刚才的解法。。。

f[i][j]=max(f[i][j-1],sum[i]-min(f[i-k][k])) k=min(2*j,i)并且k=min(2*j-1,i) 这两个都要尝试转移

然后就水过了。。

我们再来看一道画风不太一样的

[NOIP2014]飞扬的小鸟

这个题应该是众人皆知了吧。。。

不知道的话给个链接。。自己去看吧。。。题意太长。。

vijos 1907
看完题应该就能秒出暴力的方程了。。

设f[i][j]为飞到了第i个位置 高度为j的最少点击次数

下降和管子之类的细节都不是重点，我们只考虑上升部分。

f[i][j]=min(f[i-1][j-k*x[i-1]]+k)

咦 又是我们熟悉的状态N^2 转移N

然而我们发现用刚才的方法怎么也搞不掉那个k。

于是画图观察转移

然后我们发现 转移到最高处的那个转移是可以这样代替的：

咦，好神奇啊。
然后方程变成了：

f[i][j]=min(f[i-1][j-x[i-1]]+1,f[i][j-x[i-1]]+1)

然后就可以愉快的N*M DP啦。。

总结一下：

在发现一些dp的转移有较大冗余，而且复杂度较高，并且不具有决策单调性时，可以考虑这种优化。（我们就叫他相邻冗余量优化吧。。。）

考虑这种优化时，可以先看相邻项的关系，再画出转移图。。然后变形dp方程。

不过不要在这种优化上消耗过多时间，毕竟这样的比较冷门。。。

好了我写完了，上面的字都是瞎扯。。不要鄙视我傻。。

毕竟我很傻。。