我对动态规划的理解加深是从初态设计开始的,
我开始意识到动态规划并不是只能在线性情况下使用,
它同时还可以在简单环,或者是可以消除后效性的有向图上运行(有时会用自动机消除),
同时,我还初次意识到状压的实质,就像从已有板块到未知板块的入侵,有逐渐吞并也有大规模侵略。
但在此之外,它其实可以被看作线性结构来思考。
同样,DP的初态是不能被数组位所限定的,因为各种运算符的存在,其实我们可以将一些初态压缩,方便讨论而且节省空间。
然后,愤怒的小鸟又告诉我,其实对于每一个阶段,我们都可以设计合法和不合法的状态划分,这似乎像另一个DP,而后来的dpofdp也印证了这一点。
然后,我开始学习dp优化,一开始是阶段优化,比如倍增dp,意外的发现这很简单,而且很好辨别。
接着是决策优化,最简单的是数据结构,有一部分是直接用一个数据结构维护,有一些则是用可持久化数据结构维护,这里我发现了一个新做法,离线排序,然后动态维护(必须要消除后效性)。
后来,我学习了整体DP,对于树形结构,我们采用阶段合并的方式传递信息。
并且针对树形结构,我同时学习了重链剖分和长链剖分,一种将子树和链作为桶的重叠方法,正对应了上面的状态重叠。
之后我接触了单调队列优化和斜率优化,并学习了二分栈等算法,同时接触了矩阵优化,我突然发现,似乎阶段和决策都可以看成元素,组合得到答案。
之后,我尝试更深入基本算法,比如区间DP,我发现区间DP其实只用区分右端点和左端点(这是个广泛的概念,应该说是域的边界),对于阶段的划分和决策,我们可以更加自由。
然后,由bitset优化和根号分治,我发现看起来不可行的方法不一定真的行不通。
最重要的是简化状态,还有打表找性质。
为了锻炼对于更复杂状态的设计能力,我开始写树形DP,并了解了多叉树转二叉树,以及用数据结构维护转移来特殊判断的奇怪技巧,相较于一般的DP,树形在状态设计和转移上更具挑战。
然后我开始深入状态转移,通过对期望DP的研究我意外的发现,DP对数的应用超出了我以往的理解,我们可以将实数扩展到虚数(后来发现这也是FFT的精髓),或者是从低次幂的数开始维护高次幂的数异或是更朴素的说法将限制层层打开层层转移(对于多个生成函数也用到了这个思想)。
我们还可以通过剩余系对状态进行重叠。
之后我去学习了数位DP,并发现它于dpofdp本质相同。
接着,我学习了生成函数,并发现由于未知数取值可以在1 −1以内,所以可以收敛(之前学一直不知道),不难用无限和式的方法求出封闭形式(虽然更简单的是背公式),但是封闭形式基本不能看,先将可以提出去的东西简化,然后将它化成公式里面的形式就可以了。
后面我尝试看了一下博弈论,其实结合逻辑链考虑,一般是直接计算SG就可以了,挺套路。
不过对于博弈dp,就是一个决定dp值要哪个才可以的过程,可以写在纸上(推大多数转移方程都要这样)。