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

【C++贪心】P8769 [蓝桥杯 2021 国 C] 巧克力|普及+

【C++贪心】P8769 [蓝桥杯 2021 国 C] 巧克力|普及+

本文涉及知识点 C++贪心 [蓝桥杯 2021 国 C] 巧克力 题目描述 小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。 一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 x x x 天的巧克力。 输入格式 输入的第一行包含两个整数 x x x， n n n，分别表示需要吃巧克力的天数和巧克力的种类数。 接下来 n n n 行描述货架上的巧克力，其中第 i i i 行包含三个整数 a i a_i ai ， b i b_i bi

By Ne0inhk

Trae配置MinGW编译C++全攻略

好的，使用 Trae 编译 C++ 程序需要配置外部工具链（如 MinGW），以下是详细步骤： 1. 安装 MinGW * 下载：前往 MinGW-w64 官网 下载安装包（推荐选择 x86_64-win32-seh 版本）。 * 安装：运行安装程序，设置安装路径（如 C:\mingw64），确保勾选 gcc-g++ 组件。 * 配置环境变量： * 打开系统环境变量设置（Win + S 搜索“环境变量”）。 * 在 Path 变量中添加 MinGW 的 bin 目录路径（例如 C:\mingw64\bin）。 * 保存后重启 Trae 或终端使配置生效。

By Ne0inhk
【算法通关指南：数据结构和算法篇】别再用指针写链表了！数组模拟单 / 双向链表，C++ 实战超丝滑

【算法通关指南：数据结构和算法篇】别再用指针写链表了！数组模拟单 / 双向链表，C++ 实战超丝滑

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生 文章目录 * 前言 * 一、链表的概念 * 1.1 链表的定义 * 1.2 链表的分类 * 二、链表的模拟实现 * 2.1 单链表的模拟实现 * 2.1.1 定义-创建-初始化 * 2.1.2 头插 * 2.1.3 遍历链表 * 2.1.4 按值查找 * 策略一：遍历整个链表 * 策略二：使用哈希表优化 * 2.1.5 在任意位置之后插入元素 * 2.

By Ne0inhk
Qt步进电机上位机控制程序源代码：跨平台C/C++编写，支持多种端口类型与详细注释

Qt步进电机上位机控制程序源代码：跨平台C/C++编写，支持多种端口类型与详细注释

Qt步进电机上位机控制程序源代码Qt跨平台C/C++语言编写 支持串口Tcp网口Udp网络三种端口类型 提供，提供详细注释和人工讲解 1.功能介绍： 可控制步进电机的上位机程序源代码，基于Qt库，采用C/C++语言编写。 支持串口、Tcp网口、Udp网络三种端口类型，带有调试显示窗口，接收数据可实时显示。 带有配置自动保存功能，用户的配置数据会自动存储，带有超时提醒功能，如果不回复则弹框提示。 其中三个端口，采用了类的继承与派生方式编写，对外统一接口，实现多态功能，具备较强的移植性。 2.环境说明： 开发环境是Qt5.10.1，使用Qt自带的QSerialPort，使用网络的Socket编程。 源代码中包含详细注释，使用说明，设计文档等。 请将源码放到纯英文路径下再编译。 3.使用介绍： 可直接运行在可执行程序里的exe文件，操作并了解软件运行流程。 本代码产品特点： 1、尽量贴合实际应用，细节考虑周到。 2、注释完善，讲解详细，还有相关扩展知识点介绍。

By Ne0inhk