动态DP
从一道简单的问题说起
- 有一个长度为 \(n\) 的序列 \(a_i\)，每个数可以选或者不选，但相邻两个数不能同时选，最大化选出的数的和。
有一个简单的 \(dp\)，设 \(f_{i,0/1}\) 表示前 \(i\) 个数，第 \(i\) 个数是否选了的最大价值，转移时
- \(f_{i,1}=f_{i-1,0}+a_i\)
- \(f_{i,0}=\max(f_{i-1,0},f_{i-1,1})\)
现在把这个问题加强一下：
- 有一个长度为 \(n\) 的序列 \(a_i\)，每个数可以选或者不选，但相邻两个数不能同时选，最大化选出的数的和，需要支持单点修改和对区间查询。
我们可以把转移写成矩阵的形式：
\[\begin{bmatrix} f_{i,0}&f_{i,1}\\ \end{bmatrix} = \begin{bmatrix} f_{i-1,0}&f_{i-1,1}\\ \end{bmatrix} \times \begin{bmatrix} 0&a_i\\ 0&-\infty\\ \end{bmatrix} \]其中矩阵乘法定义为 \((\max,+)\) 乘法。
不妨令
\[M_i= \begin{bmatrix} 0&a_i\\ 0&-\infty\\ \end{bmatrix} \]那么答案可以写成
\[\begin{bmatrix} 0&0\\ \end{bmatrix} \times \prod\limits_{i=1}^nM_i \]现在是单点修改，区间查询，我们可以用线段树维护区间内的 \(M_i\) 的乘积，因为矩阵乘法有结合律所以这样做是正确的。
这样子就可以在 \(\Theta(n\log n)\) 复杂度内解决这个问题。
类似上面的过程，在解决动态，范围查询的动态规划问题时，用数据结构维护矩阵乘法的方式也被称为动态 dp，也可以简称为 ddp。
树上的情况
P4719 【模板】"动态 DP"&动态树分治
没有修改时，设 \(f_{x,0/1}\) 表示 \(x\) 子树内，节点 \(x\) 是否选了的最大权值和，转移是显然的：
- \(f_{x,0}=\sum\limits_{y\in son_x}\max(f_{y,0},f_{y,1})\)。
- \(f_{x,1}=\sum\limits_{y\in son_x}f_{y,0}\)。