序列 dp
引入：最大子段和
给定一个数列 \(a_1, a_2, \cdots, a_n\)（可能为负），求 \(\max\limits_{1\le l\le r\le n}\left\{\sum_{i=l}^ra_i\right\}\)。
这是一个经典的 动态规划 问题：设 \(f_{i}\) 为以 \(a_i\) 结尾的最大子段和，设 \(g_{i}\) 为前 \(i\) 个数的最大子段和。那么显然有：
f_i = \max(f_{i-1} + a_i, 0)\\
g_i = \max(f_{i-1} + a_i, g_{i-1})
\end{cases}
\]
其中 \(g\) 不对 \(0\) 取 \(\max\) 是因为必须保证非空。根据定义，答案即为 \(g_n\)。
接下来考虑它的一个加强版：
给定一个数列 \(a_1, a_2, \cdots, a_n\)（可能为负），\(q\) 次询问或修改，询问每次给定 \(x,y\) 求 \(\max\limits_{x\le l\le r\le y}\left\{\sum_{i=l}^ra_i\right\}\)；修改为将 \(a_x\) 赋值为 \(y\)。【SPOJ - GSS3】
这题有一个经典的线段树做法，维护最大前后缀和及最大子段和，这里不做描述。
笔者接下来会介绍一种更加通用的方法。
动态规划与矩阵的转化
矩阵？为什么天上掉下来这么一个东西？它和 dp 有什么联系？
一个简单的例子，考虑现在有下面这样的一个 dp：
&\begin{cases}
f_i = 3f_{i-1} + 5g_{i-1}\\
g_i = f_{i-1} + g_{i-1} + 3a_i
\end{cases} &(i>0) \\
&f_i = g_i = 0 & (i=0)
\end{aligned}
\]
然后把它写成 矩阵乘法 的形式。首先矩阵中应当有 \(f,g\) 这两项，加上 \(a_i\) 共三项。现在我们需要做的是，找到关于 \(a_i\) 的一个转移矩阵 \(A_i\)，满足：
\]
熟悉矩阵乘法的可以根据递推式很快看出来：
\]
然后我们发现，对于所有的 \(i\)，转移矩阵 \(A_i\) 只和 \(a_i\) 有关，这意味着我们可以根据给定的 \(a_1, a_2, \cdots, a_n\) 求出所有 \(A_1, A_2, \cdots, A_n\)。于是原来 dp 的过程可以转化为矩阵 \(\begin{bmatrix} f_0=1\\g_0=1 \\1\end{bmatrix}\) 左乘上这些转移矩阵 \(A
_n \times A_{n-1} \times \cdots \times A_2 \times A_1\)（注意矩阵乘法 不存在交换律 ！）
为什么要用矩阵
矩阵最广为人知的优秀性质之一就是它具有 结合律：
\]
加速递推用的 矩阵快速幂 就是利用了这种性质，从而可以用倍增或分治思想加速矩阵的幂运算。而其中的 分治 思想就是我们需要利用的。
你可能从来没有听说过在 dp 的过程中先 dp 左边一块，然后 dp 右边一块，遇上修改也很难操作，而矩阵在这方面就很可以，只要将状态转移方程搞成矩阵，只要不调换顺序怎么乘都可以。
只有多组询问的话可以离线，但加上修改的话，最好还是将分治过程实体化为 线段树 ，具体地，线段树每个结点维护对于区间的所有转移矩阵连乘的结果。
动态 dp
这种使用矩阵表示 dp 过程，并用某些数据结构维护的手法被称为 动态 dp。
如果用线段树维护区间乘积，上面那个问题就没有什么难度了。
但是在应用到 GSS3 上时又出现了一个问题，状态转移方程中都是 \(\max\)，根本无法直接转化为矩阵乘法。
广义矩阵乘法
解决方案是 重新定义矩阵乘法的规则。为了适应转移方程，我们这样定义（记为 \(*\)）：
\]
在这个基础上我们带入原式到矩阵中：
\]
似乎没有什么问题……但是我们的结合律还在嘛？答案是显然的，暴力证一下也是可以的：
\left[(A * B) * C\right]_{i, j} &= \max_{k}\{(A*B)_{i,k}+C_{k,j}\} & \left[A * (B * C)\right]_{i, j} &= \max_{k}\{C_{i,k}+(A*B)_{k,j}\} \\
&= \max_{k}\{\max_{l}\{A_{i,l}+B_{l,k}\}+C_{k,j} \} & &= \max_{k}\{A_{i, k}+\max_{l}\{B_{k,l}+C_{l,j}\}\} \\
&= \max_{k,l}\{A_{i,l} + B_{l, k} + C_{k, j} \} & &= \max_{k,l}\{A_{i,k} + B_{k,l} + C_{l,j} \}
\end{aligned}
\]
发现两边只是把 \(k, l\) 调换了个位置，本质必然还是一样的。
GSS3：单点修改、区间最大子段和
如上我们以及完成了 GSS1，那么单点修改有手就行，每次只要改掉线段树叶节点上的转移矩阵，然后一路 pushup 即可。\(O(n\log n)\)。
GSS6：带插入删除区间最大子段和
动态的序列考虑平衡树，然后没了。\(O(n\log n)\)。
GSS7：树链赋值、树链最大子段和
这个稍微复杂一些，但发现仅仅是序列上树，考虑树剖 LCT 不会。
链上赋值可以用延迟标记实现，要快速得到区间大小个相同矩阵相乘，可以直接矩阵快速幂。
注意从 \(x\) 向上的、向下到 \(y\) 的这两部分不能混淆，矩乘没有交换律，因此还要维护正逆序的矩乘结果。
加上树剖和快速幂，复杂度好像是 \(O(n\log^3 n)\) 的，而且常数很大不建议用这种写法做此题（LCT 可以试试）。
树形 dp
简单的例子：树上最大独立集
给定一颗 \(n\) 个顶点的树，点带权，选出一个点集 \(\text V\)，使得不存在两点 \(u, v\in \text V\) 在树上相邻。求选出的点权和的最大值。
还是先列出静态问题的状态转移方程：
f_{i,0} = \sum_{y\in \text{son}(x)} \max(f_{y,0},f_{y,1}) \\
f_{i,1} = \sum_{y\in \text{son}(x)} f_{y,0} \\
\end{cases}
\]
其中 \(f_{i,0},\ f_{i,1}\) 分别表示子树 \(i\) 的根不选或选的最大值。答案为 \(\max(f_{\text{root},0},f_{\text{root},1})\)。
动态最大独立集
（上接）先有 \(q\) 次操作，每次将顶点 \(x\) 点权改为 \(y\)。求出每次修改后的树上最大独立集点权和。
首先观察一个顶点 \(x\) 被修改之后，影响的是这个点到根的路径上的 dp 值。那么相当于一次链修改，但有和 GSS7 不太一样，这里求的是子树，上面的 dp 值依赖于下面的结果。
不过我们还是考虑 轻重链剖分。然后我们的树差不多就成了这样（图片来源）：
对轻重儿子分别处理：定义 \(g_{x,0/1}\) 表示不考虑 \(x\) 的重儿子， \(x\) 选或不选得到的最大点权和。那么：
g_{x,0} = \sum_{y\in \text{lightSon(x)}} \max(g_{y,0},g_{y,1}) \\
g_{x,1} = \sum_{y\in \text{lightSon(x)}} g_{y,0}
\end{cases}
\]
于是就可以用 \(g\) 去掉原来 \(f\) 式子中的 \(\Sigma\)：
f_{x,0} = g_{x,0} + \max(f_{\text{heavySon}(x),0},f_{\text{heavySon}(x),1}) \\
f_{x,1} = g_{x,1} + f_{\text{heavySon}(x),0}
\end{cases}
\]
再写成矩阵的形式，注意这里还是上面的广义矩阵乘法：
\]
看起来非常 Simple，但实际上有很多我们忽略的细节。
首先在第一遍预处理树形 dp 时，我们优先走重儿子（因此也可以在树剖的第二次 dfs 时处理），得到 \(f, g\)，然后对所有点构造转移矩阵（如上），再建立线段树即可。
对于叶子结点，只要维护一个 \(\begin{bmatrix} 0 \\ a_x \end{bmatrix}\) 即可，相当于 \(\begin{bmatrix} f_{x,0} \\ f_{x,1} \end{bmatrix}\)。
在更新时，我们先修改转移矩阵（并不是在线段树内）：将 \(g_{x,1}\) 改掉。然后在线段树上获取 原来版本 的 整条重链 的结果 \(\text{bef}\)，再将修改落实到线段树上并得到 修改后版本 整条重链 的结果 \(\text{aft}\)。之所以这么做是因为当前的重链会 作为子树中的信息影响到上面的链。
得到 \(\text{bef}\) 和 \(\text{aft}\) 之后，我们将会用它对当前点所在链顶的父亲的转移矩阵（记为 \(A\)）进行修改。根据我们构造的转移矩阵，\(A\) 的第一行前两项以及第二行第一项应该 先挖去原来这颗子树的贡献，然后算回新版本的贡献：
A_{1,1} \gets A_{1,1} - \max(\text{bef}_{1,1},\text{bef}_{2,1}) + \max(\text{aft}_{1,1},\text{aft}_{2,1}) \\
A_{1,2} \gets A_{1,2} - \max(\text{bef}_{1,1},\text{bef}_{2,1}) + \max(\text{aft}_{1,1},\text{aft}_{2,1}) \\
A_{2,1} \gets A_{2,1} - \text{bef}_{1,1} + \text{aft}_{1,1}
\end{cases}
\]
如此一路更新到根即可。
查询只要查 \(1\) 所在的重链即可。
这样做的复杂度为 \(O(n\log^2 n)\)，用 LCT 或全局平衡二叉树可以 \(O(n\log n)\)。
NOIp2018：保卫王国
求树上最小覆盖集，\(q\) 次询问，每次钦定两个点选或不选。
其实这个用 ddp 写就很 sb，因为：最小覆盖集 \(=\) 全集 \(-\) 最大独立集。
必选：点权设为 \(\infty\)；不选：设为 \(-\infty\)。
没了？没了。
其实这个题有一个优美的非 ddp 做法的：https://www.cnblogs.com/-Wallace-/p/14002280.html
Luogu P6021：洪水
给定一颗 \(n\) 个点的树，带点权，\(q\) 次操作。每次操作修改一个点权；或询问一个子树，选出一些顶点不能走，使子树根不与任意一个叶子连通的最小点权和。
设 \(f_x\) 为子树 \(x\) 的答案，那么显然有：
\]
还是考虑轻重链分治：令 \(g_x = \sum_{y\in\text{lightSon}(x)}f_y\)，于是：
\]
烦人的 \(\Sigma\) 无了，就可以写成喜闻乐见的矩阵了（注意还是广义矩乘，把 \(\max\) 换成了 \(\min\)）：
\]
在叶子结点保留初始矩阵，非叶节点保留转移矩阵，询问就查询这个点到链底。
大功告成。复杂度 \(O(n\log^2 n)\)。
小结
随便讲一讲我的学习心得以及写题时需要注意的事情。
- 所谓动态 dp 其实也没那么吓人，就是把状态转移写成了（广义）矩阵乘法的形式，利用结合律套上数据结构，从而实现修改、对部分查询 dp 值。
- 注意矩阵乘法的顺序，矩乘没有交换律。
- 树上动归做 ddp 时，单点修改会引起所有祖先的变化，通常通过比较前后两版本的差异来更新祖先的转移矩阵。
- 定义合适的矩阵乘法规则、构造转移矩阵是解题关键。
- 虽然是一种通用的方法，但是必须意识到这种方法的大常数和大码量，在考场上通常并不是最佳选择。
- 不要用 ddp 写 GSS7
后记
- 原文地址：https://www.cnblogs.com/-Wallace-/p/14036962.html
- 本文作者：@-Wallace-
- 转载请附上出处。