C++ 动态 DP（Dynamic DP）详解：从入门到实战

Ne0inhk

— 10 min read

一、什么是动态 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]))

静态 DP 可在 O (n) 时间内计算，但如果修改某个节点的权值，需要重新计算其所有祖先的 DP 值（最坏 O (n) per update），效率极低。

2. 动态 DP 的优化思路

动态 DP 的关键是将 DP 转移 “线性化”，转化为类似矩阵乘法的形式，再用数据结构维护这些 “矩阵” 的乘积，从而实现高效更新。

（1）转移关系的线性化

对于树上问题，通过树链剖分将树分解为若干条重链，每条链用线段树维护。对于每个节点，将其与子树的 DP 关系表示为一个 “转移矩阵”，矩阵的乘法规则定义为 DP 的合并逻辑。

以树上最大独立集为例，节点 u 与其子节点 v 的转移可表示为：

[ dp[u][0] ] = [ max(a, b) + max(c, d), max(a, b) + c ] [ dp[parent][0] ] [ dp[u][1] ] [ a + d, a + c ] [ dp[parent][1] ]

（此处矩阵元素为转移系数，实际定义需满足结合律，便于线段树合并）

（2）数据结构的结合
  • 树链剖分：将树划分为 O (logn) 条重链，确保任意路径的修改可分解为 O (logn) 条链的操作。
  • 线段树：每条重链用线段树维护，每个线段树节点存储对应区间的 “转移矩阵”，支持区间合并（矩阵乘法）和单点修改，时间复杂度 O (logn) per operation。

三、动态 DP 的用途

动态 DP 主要用于带动态修改的树形 DP 问题，典型场景包括：

  1. 树上最大独立集：支持修改节点权值，实时查询全局最大独立集。
  2. 树上最长路径（直径）：支持修改边权 / 点权，实时查询直径长度。
  3. 子树和相关问题：支持修改节点权值，实时查询子树内满足特定条件的和（如最大子树和）。
  4. 带修改的序列 DP：如最长上升子序列（LIS）的动态维护（需结合其他优化）。

四、模板代码：树上最大独立集的动态 DP 实现

以下是基于树链剖分 + 线段树的动态 DP 模板，解决 “支持修改节点权值，查询树上最大独立集” 问题。

1. 核心定义与数据结构

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int INF = 1e9; // 树的存储 vector<int> adj[MAXN]; int w[MAXN]; // 节点权值 // 树链剖分相关 int parent[MAXN], depth[MAXN], size_[MAXN], heavy[MAXN]; // heavy: 重儿子 int head[MAXN], pos[MAXN]; // head: 重链头, pos: 在线段树中的位置 int cur_pos; // 当前分配的pos // DP状态（静态初始值） int dp0[MAXN], dp1[MAXN]; // dp0[u]: 不选u, dp1[u]: 选u // 转移矩阵：每个节点对应一个2x2矩阵，用于合并子树的DP值 struct Matrix { int m[2][2]; Matrix() { memset(m, -0x3f, sizeof(m)); } // 矩阵乘法：合并两个子树的转移（自定义规则，满足结合律） Matrix operator*(const Matrix& other) const { Matrix res; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { res.m[i][j] = max(res.m[i][j], m[i][k] + other.m[k][j]); } } } return res; } }; // 线段树：维护重链上的矩阵乘积 struct SegmentTree { int n; vector<Matrix> tree; SegmentTree(int size) : n(size), tree(4 * size) {} // 更新线段树的一个位置 void update(int p, const Matrix& val, int node = 1, int l = 1, int r = -1) { if (r == -1) r = n; if (l == r) { tree[node] = val; return; } int mid = (l + r) / 2; if (p <= mid) update(p, val, node*2, l, mid); else update(p, val, node*2+1, mid+1, r); tree[node] = tree[node*2] * tree[node*2+1]; // 合并左右子树 } // 查询整个区间的矩阵乘积（即整条链的转移结果） Matrix query(int node = 1, int l = 1, int r = -1) { if (r == -1) r = n; return tree[node]; } };

2. 树链剖分与静态 DP 初始化

// 第一步：计算子树大小、重儿子（树链剖分预处理） int dfs1(int u, int p) { parent[u] = p; size_[u] = 1; heavy[u] = -1; int max_size = 0; for (int v : adj[u]) { if (v != p) { depth[v] = depth[u] + 1; size_[u] += dfs1(v, u); if (size_[v] > max_size) { max_size = size_[v]; heavy[u] = v; // 重儿子 } } } return size_[u]; } // 第二步：分配pos，划分重链（head[u]为链头） void dfs2(int u, int h) { head[u] = h; pos[u] = ++cur_pos; // 在线段树中的位置 if (heavy[u] != -1) { dfs2(heavy[u], h); // 重儿子延续当前链 for (int v : adj[u]) { if (v != parent[u] && v != heavy[u]) { dfs2(v, v); // 轻儿子作为新链头 } } } } // 第三步：计算静态DP值（初始状态） void dfs_dp(int u, int p) { dp1[u] = w[u]; // 选u，初始值为自身权值 dp0[u] = 0; // 不选u，初始值为0 for (int v : adj[u]) { if (v != p) { dfs_dp(v, u); dp1[u] += dp0[v]; // 选u则子节点必须不选 dp0[u] += max(dp0[v], dp1[v]); // 不选u则子节点可选可不选 } } }

3. 动态 DP 的核心：矩阵更新与维护

// 为节点u构建其对应的转移矩阵 Matrix build_matrix(int u) { Matrix mat; // 初始矩阵：仅考虑自身权值，不包含子树（子树通过线段树合并） mat.m[1][0] = w[u]; // 选u时，只能从父节点不选的状态转移（+w[u]） mat.m[1][1] = -INF; // 选u时，不能从父节点选的状态转移（非法） mat.m[0][0] = 0; // 不选u时，可从父节点不选的状态转移（初始0，后续加子树） mat.m[0][1] = 0; // 不选u时，可从父节点选的状态转移（初始0，后续加子树） // 合并轻儿子的贡献（重儿子通过线段树维护，轻儿子直接计算） for (int v : adj[u]) { if (v != parent[u] && v != heavy[u]) { // 轻儿子 mat.m[0][0] += max(dp0[v], dp1[v]); mat.m[0][1] += max(dp0[v], dp1[v]); mat.m[1][0] += dp0[v]; } } return mat; } // 更新节点u的权值后，同步更新所有相关的DP状态 void update(int u, int new_w) { w[u] = new_w; // 从u开始，沿重链向上更新所有祖先的矩阵 while (u != -1) { int h = head[u]; // 先查询旧的链头到u的矩阵（用于计算差值） Matrix old_mat = st->query(); // 简化版，实际需查询h到u的区间 // 重新构建u的矩阵 Matrix new_mat = build_matrix(u); st->update(pos[u], new_mat); // 查询新的矩阵，更新父节点的DP值 Matrix res = st->query(); // 实际需查询h到u的区间 int new_dp0 = max(res.m[0][0], res.m[0][1]); int new_dp1 = max(res.m[1][0], res.m[1][1]); // 更新u的父节点的DP值（递归向上） u = parent[h]; } } // 查询全局树的最大独立集 int query_max() { // 根节点的DP值即为答案（假设根为1） return max(dp0[1], dp1[1]); }

4. 主函数调用流程

int main() { int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> w[i]; } for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } // 初始化树链剖分 depth[1] = 0; dfs1(1, -1); cur_pos = 0; dfs2(1, 1); // 初始化静态DP dfs_dp(1, -1); // 初始化线段树（大小为cur_pos，即节点总数） st = new SegmentTree(cur_pos); for (int i = 1; i <= n; i++) { st->update(pos[i], build_matrix(i)); } // 处理查询和修改 while (q--) { int op, u, val; cin >> op; if (op == 1) { // 修改节点权值 cin >> u >> val; update(u, val); } else { // 查询最大独立集 cout << query_max() << endl; } } return 0; }

五、代码讲解

  1. 树链剖分：通过dfs1和dfs2将树划分为重链，确保任意节点到根的路径仅含 O (logn) 条链，为后续线段树优化奠定基础。
  2. 转移矩阵：Matrix的乘法定义为 DP 状态的合并规则（max++），满足结合律，因此可通过线段树维护区间乘积（即整个链的 DP 转移结果）。
  3. 动态更新：当修改节点权值时，update函数沿重链向上更新所有相关链的矩阵，通过线段树的快速合并能力，将单次修改的时间压缩到 O (log²n)。
  4. 查询操作：根节点的max(dp0[1], dp1[1])即为全局最大独立集，由于矩阵实时维护，查询可在 O (1) 时间完成（实际依赖根节点所在链的线段树查询，O (logn)）。

六、时间复杂度分析

  • 预处理：树链剖分（dfs1+dfs2）和静态 DP（dfs_dp）均为 O (n)；线段树初始化需 O (n) 时间（每个节点构建矩阵并插入线段树）。
  • 单次修改：每次修改需沿重链向上更新 O (logn) 条链，每条链的线段树更新为 O (logn)，总时间 O (log²n)。
  • 单次查询：查询根节点的 DP 值，时间 O (1)（或 O (logn)，取决于实现）。

整体来看，动态 DP 将带 q 次修改的问题时间复杂度从 O (nq) 优化到 O (n + qlog²n)，适用于 n 和 q 均较大的场景（如 n=1e5，q=1e5）。

七、总结

动态 DP 是解决动态修改 DP 问题的强大工具，其核心是：

  1. 将静态 DP 的转移关系转化为可合并的线性形式（如自定义矩阵乘法）；
  2. 结合树链剖分和线段树等数据结构，实现转移关系的高效维护；
  3. 平衡预处理和单次操作的时间复杂度，适用于大规模动态场景。

动态 DP 的实现难度较高（需熟练掌握树链剖分、线段树和自定义矩阵运算），但在处理树上动态 DP 问题时具有不可替代的优势，是算法进阶的重要知识点。

Read more

我爱学算法之—— 二分查找（下）

我爱学算法之—— 二分查找（下）

一、寻找峰值 题目解析 对于这道题，给定一个数组nums，在这数组中，可能存在多个峰值元素，我们只需找到一个峰值，然后返回峰值索引即可。 峰值元素：严格大于左右相邻的元素。 题目中给定：nums[0]和nums[n]可以看做负无穷。 算法思路 对于这道题，首先暴力解法：遍历整个数组，依次判断一个元素它是不是峰值元素。 暴力解法的时间复杂度是O(n)；并且暴力解法它并没有用到题目中给的：nums[0]和nums[n]可以看做负无穷这一个条件。 当我们遍历i位置时，有且仅有两种情况：递增/递减（题目给定 nums[i] != nums[i+1]）。 当i位置呈现递增趋势时，也就是nums[i] > nums[i+1]，题目又给出nums[0] = nums[

By Ne0inhk
【算法】动态规划中01背包问题解析

【算法】动态规划中01背包问题解析

📢博客主页：https://blog.ZEEKLOG.net/2301_779549673 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ 📢本文由 JohnKi 原创，首发于 ZEEKLOG🙉 📢未来很长，值得我们全力奔赴更美好的生活✨ 文章目录 * 🏳️‍🌈一、01 背包问题概述 * 🏳️‍🌈二、问题分析与解法 * ❤️（一）表示状态 * 🧡（二）状态转移方程 * 🧡（三）代码实现 * 🏳️‍🌈三、多种实现方式与优化 * ❤️（一）暴力搜索 * 🧡（二）记忆化搜索 * 💛（三）动态规划 * 💚（四）空间优化 * 🏳️‍🌈四、01背包例题 * ❤️[DP42 【模板】完全背包](https://www.nowcoder.com/practice/

By Ne0inhk
数据结构：双向链表（1~2）

数据结构：双向链表（1~2）

目录 前言  一、双向链表概念与结构 双向链表概念 带头双向循环链表 双向链表结构 二、实现双向链表 1.双向链表的初始化 代码逐行解析 编辑 2.双向链表的尾插 创建节点 3.双向链表的头插 4.双向链表的尾删 双向链表的判空 5.双向链表的头删 6.双向链表的销毁 借助现有实现测试： 7.双向链表查找  8.双向链表在指定位置插入 双向链表在指定位置之后插入 双向链表在指定位置之前插入  9.双向链表指定位置删除 10.总代码展示：(加入了测试代码) 三、顺序表与链表的分析 一、相同点 二、不同点（核心差异） 三、关键结论 四、链表算法题 一、移除链表元素

By Ne0inhk
《算法题讲解指南：递归，搜索与回溯算法--二叉树中的深搜》--6.计算布尔二叉树的值，7.求根节点到叶节点数字之和

《算法题讲解指南：递归，搜索与回溯算法--二叉树中的深搜》--6.计算布尔二叉树的值，7.求根节点到叶节点数字之和

🔥小叶-duck：个人主页 ❄️个人专栏：《Data-Structure-Learning》 《C++入门到进阶&自我学习过程记录》 《算法题讲解指南》--优选算法 《算法题讲解指南》--递归、搜索与回溯算法 ✨未择之路，不须回头 已择之路，纵是荆棘遍野，亦作花海遨游 目录 深度优先遍历介绍 6.计算布尔二叉树的值 题目链接： 题目描述： 题目示例： 解法(递归)： 算法思路： C++算法代码： 7.求根节点到叶节点数字之和 题目链接： 题目描述： 题目示例： 解法(dfs-前序遍历)： 算法思路： C++算法代码： 算法总结及流程解析： 结束语 深度优先遍历介绍       深度优先遍历(DFS，全称为 Depth First Traversal)，是我们树或者图这样的数据结构中常用的一种遍历算法。

By Ne0inhk