对动态 DP 和全局平衡二叉树的一点补充解释

说明:最近在帮高中竞赛教练写讲义,这是本人对讲义中动态 DP 内容的补充解释(因为主要是对知识点的理解,不太容易用通用的语言表述,也不适合作为讲义内容供读者阅读,所以用的是补充注释的形式)。写的比较抽象也比较初等,仅供意会

1. 为什么用矩阵表示转移

我们先从一般的角度,用映射的语言来表示 DP。以序列 DP 为例,假设 \(\{ \mathrm{dp}_{i}\}\) 是 DP 值数组,\(\left\{ a_{i} \right\}\) 是每个位置的信息(说明:DP 值数组可以是 \((f_i,g_i)\) 这样不止一个的;每个位置的信息 \(a_i\) 也不一定代表权值,也可以是 \((i,a_i,b_i,c_i,...)\) 这样更加复杂的信息)。

那么通常来说,一个 DP 的转移过程可以表示为如下关系式:

\[\left( \mathrm{dp}_{n},\ \mathrm{dp}_{n - 1},\ldots,\mathrm{dp}_{n - k + 1} \right) = T_{a_{n}}(\mathrm{dp}_{n - 1},\ \mathrm{dp}_{n - 2},\ldots,\mathrm{dp}_{n - k}) \]

其中 \(T_{a_{n}}\) 是一个由 \(a_{n}\) 决定的映射,表示用 \((\mathrm{dp}_{n - 1},\ \mathrm{dp}_{n - 2},\ldots,\mathrm{dp}_{n - k})\) 这些 DP 值能够确定 \(\mathrm{dp}_{n}\) 的值(将函数值写成 \(k\) 元组只是为了方便下文书写)。

这里 \(k\) 表示 \(\mathrm{dp}_{n}\) 由前面 \(k\) 个已知的 DP 值确定。在例题 1(区间最大子段和)中 \(k = 1\),即表示 \(\mathrm{dp}_{n}\) 只与 \(\mathrm{dp}_{n - 1}\) 有关,在斐波那契数列的递推关系中就可以认为是 \(k = 2\)。那么我们容易知道:

\[\begin{aligned}\left( \mathrm{dp}_{n},\ \mathrm{dp}_{n - 1},\ldots,\mathrm{dp}_{n - k + 1} \right) &= T_{a_{n}}\left( T_{a_{n - 1}}\left( \ldots\left( T_{a_{k + 1}}\left( \mathrm{dp}_{k},\mathrm{dp}_{k - 1},\ldots,\mathrm{dp}_{1} \right) \right) \right) \right) \\&= \left( T_{a_{n}} \circ T_{a_{n - 1}} \circ \cdots \circ T_{a_{k + 1}} \right)(\mathrm{dp}_{k},\mathrm{dp}_{k - 1},\ldots,\mathrm{dp}_{1})\end{aligned}\]

这里 \(\circ\) 表示映射的复合运算,而 \(\left( \mathrm{dp}_{k},\mathrm{dp}_{k - 1},\ldots,\mathrm{dp}_{1} \right)\) 可以认为就是 DP 的初值。

有时,为了快速计算最终的答案 \(\mathrm{dp}_{n}\),我们会利用映射的特殊性质,试图求出 \(T_{a_{n}} \circ T_{a_{n - 1}} \circ \cdots \circ T_{a_{k + 1}}\) 的表达式,进而计算。以斐波那契数列的递推关系为例,

\[\begin{bmatrix} {\mathrm{dp}}_{n} \\ {\mathrm{dp}}_{n - 1} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}\begin{bmatrix} \mathrm{dp}_{n - 1} \\ {\mathrm{dp}}_{n - 2} \\ \end{bmatrix}\]

此时就相当于 \(T\left( \begin{bmatrix} \mathrm{dp}_{n - 1} \\ {\mathrm{dp}}_{n - 2} \\ \end{bmatrix} \right) = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}\begin{bmatrix} \mathrm{dp}_{n - 1} \\ {\mathrm{dp}}_{n - 2} \\ \end{bmatrix} = \begin{bmatrix} {\mathrm{dp}}_{n} \\ {\mathrm{dp}}_{n - 1} \\ \end{bmatrix}\)

更一般地,所有齐次线性递推转移方程其实都可以将DP转移表示为一个矩阵乘法,此时求映射复合就相当于求矩阵乘积,这就是矩阵快速幂优化线性递推的一种解释。

对于更常见的最优化DP,有时也可以用类似的思路处理。比如例1的区间最大子段和,转移就可以描述为:

\[T_{a_{n}}\begin{pmatrix} f_{n - 1} \\ g_{n - 1} \\ \end{pmatrix} = \begin{pmatrix} \max\left\{ f_{n - 1} + a_{n},a_{n} \right\} \\ \max\left\{ f_{n - 1} + a_{n},a_{n},g_{n - 1} \right\} \\ \end{pmatrix} = \begin{pmatrix} f_{n} \\ g_{n} \\ \end{pmatrix}\]

\(\left( \max, + \right)\) 广义矩阵乘法,可以将其写为矩阵乘法的形式,此处不再重复。写为矩阵乘法后,就利用矩阵乘法的结合律,进而用数据结构维护。

以上虽然都是用矩阵乘法的形式处理,但实质上,是因为这些转移对应的映射 \(\mathbf{T}\) 以及映射的复合都满足某些特殊性质,进而才能够用矩阵表示。回顾例 1 的另一种线段树做法,维护区间和、区间最大前缀和、最大后缀和、最大子段和这四个信息,其实就是在维护转移映射合并后的结果,所以它虽然没有显式出现矩阵乘法,但其实也能算作动态DP。

一般来说,如果转移对应的映射及其复合(或者说多个转移"合并"后)能够满足某些特殊性质,使其能够用少量信息表示(例如例1的四个区间信息,再例如若干次线性递推能够用多个矩阵的乘积表示),并且合并过程也比较容易,我们就能够用分治思想来对这些映射进行复合运算。体现在线性递推上,就是矩阵快速幂;如果带修改,那么用线段树就能很方便地维护一个映射变化,造成的复合运算结果的改变。

其中,能够分治计算依赖的是映射复合的结合律(这是自然成立的)。而真正需要注意的其实并非结合律,而是满足"特殊性质"映射对复合运算的"封闭性"(此处略去解释)。【所以,矩阵只是一种易于理解、易于推导的转移形式,矩阵乘法并不是本质的,分治思想才是解决问题的核心】

2. 如何将序列问题的解法迁移到树上问题

上文提到的方法只针对序列 DP,对于树上问题,我们通常是采用链分治的方式。对于一条重链,将每个结点轻儿子的信息合并到这个结点上(视作这个结点的信息),然后就可以在重链上用序列 DP 的方式处理了。

至于链分治的具体方式,就有三种常见方法(树剖+线段树;LCT;全局平衡二叉树),其中全局平衡二叉树的理论复杂度和实际表现都最优。

链分治的思想也可以迁移到更广泛的问题,例如链分治FFT解决部分计数问题、链分治闵可夫斯基和解决凸性DP问题(典例——树上最大边权k-匹配问题CFGym 102331J)。解决这些问题应用到的核心性质是——经过重链条数 / 全局平衡二叉树深度为 \(O(\log n)\)

这里补充说明一点:全局平衡二叉树实际上就是在重链剖分基础上,将“将重链分为两半”的分治方式,变成了“按照轻儿子的总 size + 1 为权重来分重链”的分治方式。而具体的维护细节(只是分治而不需要保留结构 or 需要用数据结构维护分治结构;线段树 or 平衡树;是否 leafy)和树链剖分都是没有实际区别的。

热门相关:我有一座恐怖屋   本法官萌萌哒   大妆   今天也没变成玩偶呢   拒嫁豪门,前妻太抢手