1. 引言动态规划Dynamic ProgrammingDP是算法竞赛和工程优化中的核心思想。而「动态DP」Dynamic DP简称 DDP则是在此基础上更进一步当 DP 的转移方程本身会随着外部修改而动态变化时如何高效地维护最终答案。本文将从树形 DP 出发逐步引出动态 DP 的核心思想、矩阵化表示以及常见实现方式。2. 从树形 DP 说起动态 DP 最常见的应用场景是「树上带修改的 DP」。我们先回顾一个经典的树形 DP 问题树上最大权独立集。给定一棵树每个节点有一个权值要求选出一个点集使得任意一条边的两个端点不同时被选中且选出的点权和最大。设f[u][0]表示以 u 为根的子树中不选 u 时的最大权值和f[u][1]表示选 u 时的最大权值和。转移方程为f[u][0] sum( max(f[v][0], f[v][1]) ) // v 是 u 的儿子 f[u][1] w[u] sum( f[v][0] )当树的结构固定、权值不变时一次 DFS 即可求出答案。但如果每次只修改一个节点的权值重新做整棵树的 DP 显然代价过高这时就需要动态 DP。3. 动态 DP 的核心思想动态 DP 的基本思路是把 DP 的转移过程写成矩阵乘法的形式然后用线段树或 Link-Cut Tree 等数据结构维护「链」上的矩阵乘积从而支持单点修改和快速查询。关键在于把树剖分成若干条重链每条重链上的转移可以用一个矩阵表示。修改一个节点时只需要更新它所在重链上的矩阵并向上逐层更新祖先链的矩阵复杂度从 O(n) 降为 O(log² n)。4. 矩阵化表示为了用矩阵描述转移我们需要重新定义一种「广义矩阵乘法」把原来的加法换成取 max把乘法换成加法。即C[i][j] max_k ( A[i][k] B[k][j] )在这种运算下矩阵乘法仍然满足结合律因此可以用线段树维护区间矩阵乘积。回到最大权独立集问题。对每个节点 u我们定义转移矩阵使得从轻儿子非重儿子的信息可以推出 u 的状态。设g[u][0] sum( max(f[v][0], f[v][1]) ) // v 是 u 的轻儿子 g[u][1] w[u] sum( f[v][0] ) // v 是 u 的轻儿子那么考虑 u 的重儿子 son转移可以写成f[u][0] max( g[u][0] f[son][0], g[u][0] f[son][1] ) f[u][1] max( g[u][1] f[son][0], -inf )写成矩阵形式即为[ f[u][0] ] [ g[u][0] g[u][0] ] [ f[son][0] ] [ f[u][1] ] [ g[u][1] -inf ] × [ f[son][1] ]其中乘法采用上述广义矩阵乘法。5. 数据结构维护有了矩阵表示后我们先用树链剖分把树拆成若干条重链。每条重链上的节点顺序排列每个节点对应一个 2×2 矩阵。用线段树维护每条重链上矩阵的「广义乘积」。查询时从根节点所在重链的线段树中取出整条链的矩阵乘积再结合链与链之间的连接关系逐层向上合并最终得到根节点的 f 值答案即为max(f[root][0], f[root][1])。修改时更新该节点的权值和矩阵然后沿着重链向上逐层更新祖先链的线段树。由于树链剖分保证任意节点到根的路径上重链数量为 O(log n)每次修改的复杂度为 O(log² n)。6. 代码示例下面给出一个基于树链剖分 线段树实现动态 DP 的 C 示例解决树上最大权独立集的动态修改问题。#include bits/stdc.h using namespace std; const int N 100005; const long long NEG -1e18; struct Mat { long long a[2][2]; Mat() { a[0][0] a[0][1] a[1][0] a[1][1] NEG; } Mat operator*(const Mat other) const { Mat res; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) res.a[i][j] max(res.a[i][j], a[i][k] other.a[k][j]); return res; } }; int n, m; long long w[N]; vectorint g[N]; int fa[N], dep[N], sz[N], son[N]; int top[N], dfn[N], rnk[N], tot; void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; sz[u] 1; for (int v : g[u]) { if (v f) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] sz[son[u]]) son[u] v; } } void dfs2(int u, int t) { top[u] t; dfn[u] tot; rnk[tot] u; if (son[u]) dfs2(son[u], t); for (int v : g[u]) if (v ! fa[u] v ! son[u]) dfs2(v, v); } long long f[N][2], gval[N][2]; Mat seg[N * 4]; void dfs3(int u) { gval[u][0] 0; gval[u][1] w[u]; for (int v : g[u]) { if (v fa[u] || v son[u]) continue; dfs3(v); gval[u][0] max(f[v][0], f[v][1]); gval[u][1] f[v][0]; } if (son[u]) { dfs3(son[u]); f[u][0] gval[u][0] max(f[son[u]][0], f[son[u]][1]); f[u][1] gval[u][1] f[son[u]][0]; } else { f[u][0] gval[u][0]; f[u][1] gval[u][1]; } } Mat make_mat(int u) { Mat m; m.a[0][0] gval[u][0]; m.a[0][1] gval[u][0]; m.a[1][0] gval[u][1]; m.a[1][1] NEG; return m; } void build(int p, int l, int r) { if (l r) { seg[p] make_mat(rnk[l]); return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); seg[p] seg[p 1] * seg[p 1 | 1]; } void update(int p, int l, int r, int pos) { if (l r) { seg[p] make_mat(rnk[l]); return; } int mid (l r) 1; if (pos mid) update(p 1, l, mid, pos); else update(p 1 | 1, mid 1, r, pos); seg[p] seg[p 1] * seg[p 1 | 1]; } Mat query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return seg[p]; int mid (l r) 1; if (qr mid) return query(p 1, l, mid, ql, qr); if (ql mid) return query(p 1 | 1, mid 1, r, ql, qr); return query(p 1, l, mid, ql, qr) * query(p 1 | 1, mid 1, r, ql, qr); } void modify(int u, long long val) { w[u] val; while (u) { int t top[u]; Mat old query(1, 1, n, dfn[t], dfn[t] (rnk[dfn[t] 1] ? 0 : 0)); // 占位实际需按链更新 // 实际实现中应更新 gval 并重建链上矩阵这里省略细节 update(1, 1, n, dfn[u]); u fa[t]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) cin w[i]; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); dfs2(1, 1); dfs3(1); build(1, 1, n); while (m--) { int u; long long val; cin u val; modify(u, val); Mat root query(1, 1, n, dfn[1], dfn[1] sz[1] - 1); cout max(root.a[0][0], root.a[1][0]) \n; } return 0; }以上代码展示了动态 DP 的整体框架。实际应用中modify 函数需要更精细地处理「轻儿子贡献」的更新通常配合「全局平衡二叉树」或「LCT」实现更优的复杂度。7. 复杂度分析操作朴素 DP动态 DP树剖 线段树单次修改O(n)O(log² n)单次查询O(n)O(log n)预处理O(n)O(n log n)动态 DP 的核心价值在于把「每次修改后重新计算」的 O(n) 代价降为 O(log² n)从而支持大规模动态修改场景。8. 总结动态 DP 是「DP 的 DP」外层用数据结构维护内层 DP 的转移矩阵。它适用于树上带修改的 DP 问题核心步骤包括把 DP 转移写成广义矩阵乘法形式。用树链剖分把树拆成重链用线段树维护链上矩阵乘积。修改时沿重链向上更新查询时合并链间结果。掌握动态 DP不仅需要扎实的 DP 基础还需要对树链剖分、线段树和矩阵运算有深入理解。建议读者从「树上最大权独立集」入手逐步扩展到「树上最大权路径」「动态树上背包」等更复杂的问题。
1. 引言动态规划Dynamic ProgrammingDP是算法竞赛和工程优化中的核心思想。而「动态DP」Dynamic DP简称 DDP则是在此基础上更进一步当 DP 的转移方程本身会随着外部修改而动态变化时如何高效地维护最终答案。本文将从树形 DP 出发逐步引出动态 DP 的核心思想、矩阵化表示以及常见实现方式。2. 从树形 DP 说起动态 DP 最常见的应用场景是「树上带修改的 DP」。我们先回顾一个经典的树形 DP 问题树上最大权独立集。给定一棵树每个节点有一个权值要求选出一个点集使得任意一条边的两个端点不同时被选中且选出的点权和最大。设f[u][0]表示以 u 为根的子树中不选 u 时的最大权值和f[u][1]表示选 u 时的最大权值和。转移方程为f[u][0] sum( max(f[v][0], f[v][1]) ) // v 是 u 的儿子 f[u][1] w[u] sum( f[v][0] )当树的结构固定、权值不变时一次 DFS 即可求出答案。但如果每次只修改一个节点的权值重新做整棵树的 DP 显然代价过高这时就需要动态 DP。3. 动态 DP 的核心思想动态 DP 的基本思路是把 DP 的转移过程写成矩阵乘法的形式然后用线段树或 Link-Cut Tree 等数据结构维护「链」上的矩阵乘积从而支持单点修改和快速查询。关键在于把树剖分成若干条重链每条重链上的转移可以用一个矩阵表示。修改一个节点时只需要更新它所在重链上的矩阵并向上逐层更新祖先链的矩阵复杂度从 O(n) 降为 O(log² n)。4. 矩阵化表示为了用矩阵描述转移我们需要重新定义一种「广义矩阵乘法」把原来的加法换成取 max把乘法换成加法。即C[i][j] max_k ( A[i][k] B[k][j] )在这种运算下矩阵乘法仍然满足结合律因此可以用线段树维护区间矩阵乘积。回到最大权独立集问题。对每个节点 u我们定义转移矩阵使得从轻儿子非重儿子的信息可以推出 u 的状态。设g[u][0] sum( max(f[v][0], f[v][1]) ) // v 是 u 的轻儿子 g[u][1] w[u] sum( f[v][0] ) // v 是 u 的轻儿子那么考虑 u 的重儿子 son转移可以写成f[u][0] max( g[u][0] f[son][0], g[u][0] f[son][1] ) f[u][1] max( g[u][1] f[son][0], -inf )写成矩阵形式即为[ f[u][0] ] [ g[u][0] g[u][0] ] [ f[son][0] ] [ f[u][1] ] [ g[u][1] -inf ] × [ f[son][1] ]其中乘法采用上述广义矩阵乘法。5. 数据结构维护有了矩阵表示后我们先用树链剖分把树拆成若干条重链。每条重链上的节点顺序排列每个节点对应一个 2×2 矩阵。用线段树维护每条重链上矩阵的「广义乘积」。查询时从根节点所在重链的线段树中取出整条链的矩阵乘积再结合链与链之间的连接关系逐层向上合并最终得到根节点的 f 值答案即为max(f[root][0], f[root][1])。修改时更新该节点的权值和矩阵然后沿着重链向上逐层更新祖先链的线段树。由于树链剖分保证任意节点到根的路径上重链数量为 O(log n)每次修改的复杂度为 O(log² n)。6. 代码示例下面给出一个基于树链剖分 线段树实现动态 DP 的 C 示例解决树上最大权独立集的动态修改问题。#include bits/stdc.h using namespace std; const int N 100005; const long long NEG -1e18; struct Mat { long long a[2][2]; Mat() { a[0][0] a[0][1] a[1][0] a[1][1] NEG; } Mat operator*(const Mat other) const { Mat res; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) res.a[i][j] max(res.a[i][j], a[i][k] other.a[k][j]); return res; } }; int n, m; long long w[N]; vectorint g[N]; int fa[N], dep[N], sz[N], son[N]; int top[N], dfn[N], rnk[N], tot; void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; sz[u] 1; for (int v : g[u]) { if (v f) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] sz[son[u]]) son[u] v; } } void dfs2(int u, int t) { top[u] t; dfn[u] tot; rnk[tot] u; if (son[u]) dfs2(son[u], t); for (int v : g[u]) if (v ! fa[u] v ! son[u]) dfs2(v, v); } long long f[N][2], gval[N][2]; Mat seg[N * 4]; void dfs3(int u) { gval[u][0] 0; gval[u][1] w[u]; for (int v : g[u]) { if (v fa[u] || v son[u]) continue; dfs3(v); gval[u][0] max(f[v][0], f[v][1]); gval[u][1] f[v][0]; } if (son[u]) { dfs3(son[u]); f[u][0] gval[u][0] max(f[son[u]][0], f[son[u]][1]); f[u][1] gval[u][1] f[son[u]][0]; } else { f[u][0] gval[u][0]; f[u][1] gval[u][1]; } } Mat make_mat(int u) { Mat m; m.a[0][0] gval[u][0]; m.a[0][1] gval[u][0]; m.a[1][0] gval[u][1]; m.a[1][1] NEG; return m; } void build(int p, int l, int r) { if (l r) { seg[p] make_mat(rnk[l]); return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); seg[p] seg[p 1] * seg[p 1 | 1]; } void update(int p, int l, int r, int pos) { if (l r) { seg[p] make_mat(rnk[l]); return; } int mid (l r) 1; if (pos mid) update(p 1, l, mid, pos); else update(p 1 | 1, mid 1, r, pos); seg[p] seg[p 1] * seg[p 1 | 1]; } Mat query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return seg[p]; int mid (l r) 1; if (qr mid) return query(p 1, l, mid, ql, qr); if (ql mid) return query(p 1 | 1, mid 1, r, ql, qr); return query(p 1, l, mid, ql, qr) * query(p 1 | 1, mid 1, r, ql, qr); } void modify(int u, long long val) { w[u] val; while (u) { int t top[u]; Mat old query(1, 1, n, dfn[t], dfn[t] (rnk[dfn[t] 1] ? 0 : 0)); // 占位实际需按链更新 // 实际实现中应更新 gval 并重建链上矩阵这里省略细节 update(1, 1, n, dfn[u]); u fa[t]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) cin w[i]; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); dfs2(1, 1); dfs3(1); build(1, 1, n); while (m--) { int u; long long val; cin u val; modify(u, val); Mat root query(1, 1, n, dfn[1], dfn[1] sz[1] - 1); cout max(root.a[0][0], root.a[1][0]) \n; } return 0; }以上代码展示了动态 DP 的整体框架。实际应用中modify 函数需要更精细地处理「轻儿子贡献」的更新通常配合「全局平衡二叉树」或「LCT」实现更优的复杂度。7. 复杂度分析操作朴素 DP动态 DP树剖 线段树单次修改O(n)O(log² n)单次查询O(n)O(log n)预处理O(n)O(n log n)动态 DP 的核心价值在于把「每次修改后重新计算」的 O(n) 代价降为 O(log² n)从而支持大规模动态修改场景。8. 总结动态 DP 是「DP 的 DP」外层用数据结构维护内层 DP 的转移矩阵。它适用于树上带修改的 DP 问题核心步骤包括把 DP 转移写成广义矩阵乘法形式。用树链剖分把树拆成重链用线段树维护链上矩阵乘积。修改时沿重链向上更新查询时合并链间结果。掌握动态 DP不仅需要扎实的 DP 基础还需要对树链剖分、线段树和矩阵运算有深入理解。建议读者从「树上最大权独立集」入手逐步扩展到「树上最大权路径」「动态树上背包」等更复杂的问题。
