一、什么是动态 DP?
动态 DP(Dynamic DP,简称 DDP)是一种结合了动态规划(DP)和数据结构优化的高级算法。它主要解决带动态修改的 DP 问题——当问题中的参数(如节点权值、边权)发生变化时,能够高效更新 DP 结果,而无需重新计算整个 DP 过程。
普通的静态 DP 适用于参数固定的场景(如一次性计算树上的最大独立集),但如果参数频繁修改(如多次修改节点权值后重新求最大独立集),静态 DP 会因重复计算导致效率极低(时间复杂度可能从 O(n) 退化到 O(nq),q 为修改次数)。
动态 DP 的核心思想是:将 DP 状态的转移关系转化为可被数据结构(如线段树、树链剖分)维护的形式,通过数据结构的高效更新能力,将单次修改/查询的时间复杂度从 O(n) 优化到 O(log²n) 级别。
二、基础思路:从静态 DP 到动态 DP
1. 静态 DP 的局限性
以树上最大独立集为例,先回顾静态 DP 的解法:
- 定义状态:对每个节点 u,
dp[u][0]表示不选 u 时的最大独立集(子树内),dp[u][1]表示选 u 时的最大独立集。 - 转移方程:
- 选 u 时,子节点 v 必须不选:
dp[u][1] = w[u] + sum(dp[v][0])(w[u] 为 u 的权值) - 不选 u 时,子节点 v 可选可不选:
dp[u][0] = sum(max(dp[v][0], dp[v][1]))
- 选 u 时,子节点 v 必须不选:
静态 DP 可在 O(n) 时间内计算,但如果修改某个节点的权值,需要重新计算其所有祖先的 DP 值(最坏 O(n) per update),效率极低。
2. 动态 DP 的优化思路
动态 DP 的关键是将 DP 转移'线性化',转化为类似矩阵乘法的形式,再用数据结构维护这些'矩阵'的乘积,从而实现高效更新。
(1)转移关系的线性化
对于树上问题,通过树链剖分将树分解为若干条重链,每条链用线段树维护。对于每个节点,将其与子树的 DP 关系表示为一个'转移矩阵',矩阵的乘法规则定义为 DP 的合并逻辑。
以树上最大独立集为例,节点 u 与其子节点 v 的转移可表示为:
// 转移关系示意
// | dp[u][0] | | M00 M01 | | dp[parent][0] |
// | dp[u][1] | = | M10 M11 | * | dp[parent][1] |
(此处矩阵元素为转移系数,实际定义需满足结合律,便于线段树合并)
(2)数据结构的结合
- 树链剖分:将树划分为 O(log n) 条重链,确保任意路径的修改可分解为 O(log n) 条链的操作。
- 线段树:每条重链用线段树维护,每个线段树节点存储对应区间的'转移矩阵',支持区间合并(矩阵乘法)和单点修改,时间复杂度 O(log n) per operation。
三、动态 DP 的用途
动态 DP 主要用于带动态修改的树形 DP 问题,典型场景包括:
- 树上最大独立集:支持修改节点权值,实时查询全局最大独立集。
- 树上最长路径(直径):支持修改边权/点权,实时查询直径长度。
- 子树和相关问题:支持修改节点权值,实时查询子树内满足特定条件的和(如最大子树和)。
- 带修改的序列 DP:如最长上升子序列(LIS)的动态维护(需结合其他优化)。
四、模板代码:树上最大独立集的动态 DP 实现
以下是基于树链剖分 + 线段树的动态 DP 模板,解决'支持修改节点权值,查询树上最大独立集'问题。

