本文的网课内容学习自B站左程云老师的算法详解课程旨在对其中的知识进行整理和分享~网课链接算法讲解079【必备】树型dp-下_哔哩哔哩_bilibili一.到达首都的最少油耗题目到达首都的最少油耗算法原理问题描述给定一棵树无向无环图和每个节点对应的字符寻找最长的路径要求路径上任意相邻节点的字符都不相同。整体原理采用后序遍历递归处理自底向上计算每个子树的最长有效路径通过维护两个关键值来寻找全局最优解。具体步骤构建树结构使用邻接表存储树形结构根据parent数组建立父子关系定义信息类maxPathFromHead必须从当前节点出发的最长有效路径maxPath当前子树中的最长有效路径可能不包含当前节点递归处理每个子树叶子节点直接返回(1,1)非叶子节点 a) 收集所有子节点信息 b) 维护最长(max1)和次长(max2)有效子路径 c) 确保相邻节点字符不同计算当前节点信息maxPathFromHead max1 1maxPath max(子树maxPath, max1 max2 1)最终结果根节点的maxPath即为全局解关键点解释双值维护maxPathFromHead用于向上传递maxPath记录全局最优字符比较只在相邻字符不同时考虑子路径路径组合通过max1和max2计算可能的最长路径复杂度分析时间复杂度O(n)每个节点处理一次空间复杂度O(n)存储树结构和递归栈示例输入parent [-1,0,0,1,1,2] s aabccb树结构a(0)/ \a(1) b(2)/ \ \c(3) c(4) b(5)处理过程节点3/4/5返回(1,1)节点1max11节点3max21节点4返回(2,3)路径3-1-4节点2max11节点5返回(2,2)根节点0max12节点1max22节点2最长路径5如3-1-0-2-5总结树形DP的典型应用通过双值维护实现高效计算严格遵循相邻字符不同的约束适用于树形结构的最长路径问题代码实现import java.util.ArrayList; // 相邻字符不同的最长路径 // 给你一棵 树即一个连通、无向、无环图根节点是节点 0 // 这棵树由编号从 0 到 n - 1 的 n 个节点组成 // 用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树 // 其中 parent[i] 是节点 i 的父节点 // 由于节点 0 是根节点所以 parent[0] -1 // 另给你一个字符串 s 长度也是 n 其中 s[i] 表示分配给节点 i 的字符 // 请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 // 并返回该路径的长度 // 测试链接 : https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/ public class Code02_LongestPathWithDifferentAdjacent { public static int longestPath(int[] parent, String str) { int n parent.length; char[] s str.toCharArray(); ArrayListArrayListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int i 1; i n; i) { graph.get(parent[i]).add(i); } return f(s, graph, 0).maxPath; } public static class Info { public int maxPathFromHead; // 一定要从头节点出发的情况下相邻字符不等的最长路径长度 public int maxPath; // 整棵树上相邻字符不等的最长路径长度 public Info(int a, int b) { maxPathFromHead a; maxPath b; } } public static Info f(char[] s, ArrayListArrayListInteger graph, int u) { if (graph.get(u).isEmpty()) { // u节点是叶 return new Info(1, 1); } int max1 0; // 下方最长链 int max2 0; // 下方次长链 int maxPath 1; for (int v : graph.get(u)) { Info nextInfo f(s, graph, v); maxPath Math.max(maxPath, nextInfo.maxPath); if (s[u] ! s[v]) { if (nextInfo.maxPathFromHead max1) { max2 max1; max1 nextInfo.maxPathFromHead; } else if (nextInfo.maxPathFromHead max2) { max2 nextInfo.maxPathFromHead; } } } int maxPathFromHead max1 1; maxPath Math.max(maxPath, max1 max2 1); return new Info(maxPathFromHead, maxPath); } }二.相邻字符不同的最长路径题目相邻字符不同的最长路径算法原理问题描述给定一棵树结构无向无环图和每个节点对应的字符要求找出树中最长的路径该路径需满足任意相邻节点的字符都不相同。路径长度由路径上的节点数量决定。整体原理采用深度优先搜索DFS的后序遍历方式自底向上递归计算每个子树的信息。通过维护两个关键值来寻找全局最优解从当前节点出发的最长有效路径maxPathFromHead当前子树内的最长有效路径maxPath具体步骤树结构构建使用邻接表ArrayListArrayListInteger存储树形结构根据parent数组建立父子关系parent[i]表示节点i的父节点递归定义信息类class Info {int maxPathFromHead; // 必须包含当前节点的最长有效路径int maxPath; // 当前子树中的最长有效路径可不含当前节点}递归处理每个节点基本情况叶子节点直接返回(1,1)递归情况 a) 初始化max1最长子路径、max2次长子路径和maxPath b) 遍历所有子节点更新全局maxPath若当前节点与子节点字符不同更新max1和max2 c) 计算当前节点信息maxPathFromHead max1 1maxPath max(子树maxPath, max1 max2 1)结果获取从根节点开始递归最终结果为根节点的maxPath值关键点说明双值维护机制maxPathFromHead保证路径连续性用于向上传递maxPath记录全局最优解可能来自子树或当前路径组合字符差异检查只在当前节点与子节点字符不同时考虑子路径确保路径中相邻节点字符不同路径组合逻辑最长路径可能由两条最长子路径通过当前节点连接而成max1 max2 1同时考虑不经过当前节点的子树路径复杂度分析时间复杂度O(n)每个节点仅处理一次空间复杂度O(n)用于存储树结构和递归栈示例输入parent [-1,0,0,1,1,2] s aabccb树结构a(0)/ \a(1) b(2)/ \ \c(3) c(4) b(5)处理过程节点3/4/5叶子节点返回(1,1)节点1max11节点3或4max21maxPathFromHead2a→cmaxPath3c→a→c返回(2,3)节点2max11节点5maxPathFromHead2b→b不合法实际为1需要修正返回(1,1)注此处示例处理可能有误实际b(2)与b(5)字符相同应跳过根节点0max12节点1max20maxPathFromHead3a→a→c不合法实际应为a→b2maxPathmax(3,201)3最终最长路径3如c→a→b注示例中字符相同的情况需要特殊处理实际代码已正确处理总结适用场景树形结构中的条件约束路径问题算法优势通过一次遍历完成计算严格保证相邻节点字符不同的约束高效找到全局最优解扩展性可应用于其他树形路径约束问题该算法通过巧妙的双值维护和路径组合逻辑高效解决了树形结构中带字符约束的最长路径问题。其核心在于后序遍历的信息传递和全局最优解的动态维护。代码实现import java.util.ArrayList; // 相邻字符不同的最长路径 // 给你一棵 树即一个连通、无向、无环图根节点是节点 0 // 这棵树由编号从 0 到 n - 1 的 n 个节点组成 // 用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树 // 其中 parent[i] 是节点 i 的父节点 // 由于节点 0 是根节点所以 parent[0] -1 // 另给你一个字符串 s 长度也是 n 其中 s[i] 表示分配给节点 i 的字符 // 请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 // 并返回该路径的长度 // 测试链接 : https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/ public class Code02_LongestPathWithDifferentAdjacent { public static int longestPath(int[] parent, String str) { int n parent.length; char[] s str.toCharArray(); ArrayListArrayListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int i 1; i n; i) { graph.get(parent[i]).add(i); } return f(s, graph, 0).maxPath; } public static class Info { public int maxPathFromHead; // 一定要从头节点出发的情况下相邻字符不等的最长路径长度 public int maxPath; // 整棵树上相邻字符不等的最长路径长度 public Info(int a, int b) { maxPathFromHead a; maxPath b; } } public static Info f(char[] s, ArrayListArrayListInteger graph, int u) { if (graph.get(u).isEmpty()) { // u节点是叶 return new Info(1, 1); } int max1 0; // 下方最长链 int max2 0; // 下方次长链 int maxPath 1; for (int v : graph.get(u)) { Info nextInfo f(s, graph, v); maxPath Math.max(maxPath, nextInfo.maxPath); if (s[u] ! s[v]) { if (nextInfo.maxPathFromHead max1) { max2 max1; max1 nextInfo.maxPathFromHead; } else if (nextInfo.maxPathFromHead max2) { max2 nextInfo.maxPathFromHead; } } } int maxPathFromHead max1 1; maxPath Math.max(maxPath, max1 max2 1); return new Info(maxPathFromHead, maxPath); } }三.移除子树后的二叉树高度题目移除子树后的二叉树高度算法原理问题描述给定一棵二叉树和查询数组queries对于每个查询queries[i]需要临时移除以该值为根节点的子树后计算剩余树的高度。所有查询相互独立每次查询后树会恢复初始状态。整体原理DFS预处理通过深度优先搜索记录每个节点的深度、子树大小和dfn序号前缀/后缀最大值数组构建左右两侧的最大深度数组用于快速查询查询处理利用预处理信息快速计算移除任意子树后的树高具体步骤DFS预处理阶段为每个节点分配dfn序号深度优先编号记录每个节点的深度从根节点到该节点的边数计算每个节点的子树大小包括自身递归公式size[i] 1 size[left] size[right]构建极值数组maxl[i]表示dfn前i个节点的最大深度maxr[i]表示dfn后i个节点的最大深度填充方式maxl[i] max(maxl[i-1], deep[i]) maxr[i] max(maxr[i1], deep[i])查询处理阶段对于查询节点q a) 获取其dfn序号pos dfn[q]b) 左半部分最大深度maxl[pos-1]c) 右半部分最大深度maxr[pos size[pos]]d) 剩余树高max(leftMax, rightMax)关键点说明dfn序号的妙用将树结构线性化子树节点在dfn数组中连续存储极值数组的意义实现O(1)时间复杂度的区间最大深度查询避免每次查询都重新遍历树结构独立查询处理预处理阶段捕获树的完整结构信息查询阶段只需组合预计算的值复杂度分析时间复杂度预处理O(n)DFS遍历查询处理O(m)m次O(1)查询总计O(n m)空间复杂度O(n)存储dfn、deep、size等数组示例假设二叉树1(3)/ \2(1) 3(2)/ \4(0) 5(0)括号内为节点值预处理结果dfn [0,1,2,3,4,5] 索引为节点值deep [0,1,2,1,2,2] dfn序号的深度size [5,3,1,1,1,1] 子树大小查询queries的处理查询节点2的dfn2左半部分maxl1右半部分从dfn235开始maxr0剩余树高max(1,0)1总结适用场景需要频繁查询子树移除后信息的树形问题算法优势通过线性化预处理实现高效查询完美处理独立查询要求空间换时间的经典应用扩展性可应用于其他子树统计类问题该算法通过巧妙的预处理和极值数组设计将复杂的树形查询问题转化为高效的线性查询问题展示了算法设计中空间与时间权衡的精妙运用。代码实现// 移除子树后的二叉树高度 // 给你一棵 二叉树 的根节点 root 树中有 n 个节点 // 每个节点都可以被分配一个从 1 到 n 且互不相同的值 // 另给你一个长度为 m 的数组 queries // 你必须在树上执行 m 个 独立 的查询其中第 i 个查询你需要执行以下操作 // 从树中 移除 以 queries[i] 的值作为根节点的子树 // 题目所用测试用例保证 queries[i] 不等于根节点的值 // 返回一个长度为 m 的数组 answer // 其中 answer[i] 是执行第 i 个查询后树的高度 // 注意 // 查询之间是独立的所以在每个查询执行后树会回到其初始状态 // 树的高度是从根到树中某个节点的 最长简单路径中的边数 // 测试链接 : https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/ public class Code03_HeightRemovalQueries { // 不要提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static final int MAXN 100010; // 下标为节点的值 public static int[] dfn new int[MAXN]; // 下标为dfn序号 public static int[] deep new int[MAXN]; // 下标为dfn序号 public static int[] size new int[MAXN]; public static int[] maxl new int[MAXN]; public static int[] maxr new int[MAXN]; public static int dfnCnt; public static int[] treeQueries(TreeNode root, int[] queries) { dfnCnt 0; f(root, 0); for (int i 1; i dfnCnt; i) { maxl[i] Math.max(maxl[i - 1], deep[i]); } maxr[dfnCnt 1] 0; for (int i dfnCnt; i 1; i--) { maxr[i] Math.max(maxr[i 1], deep[i]); } int m queries.length; int[] ans new int[m]; for (int i 0; i m; i) { int leftMax maxl[dfn[queries[i]] - 1]; int rightMax maxr[dfn[queries[i]] size[dfn[queries[i]]]]; ans[i] Math.max(leftMax, rightMax); } return ans; } // 来到x节点从头节点到x节点经过了k条边 public static void f(TreeNode x, int k) { int i dfnCnt; dfn[x.val] i; deep[i] k; size[i] 1; if (x.left ! null) { f(x.left, k 1); size[i] size[dfn[x.left.val]]; } if (x.right ! null) { f(x.right, k 1); size[i] size[dfn[x.right.val]]; } } }四.从树中删除边的最小分数题目从树中删除边的最小分数算法原理问题描述给定一棵无向连通树每个节点有一个整数值。要求删除两条不同的边将树分成三个连通组件计算每个组件所有节点值的异或值找出最大异或值与最小异或值的最小可能差值。整体原理DFS预处理通过深度优先搜索为节点分配dfn序号并计算每个子树的异或和边对枚举枚举所有可能的边对组合快速计算利用dfn序和子树利用dfn序和子树信息快速确定三种分割情况分数计算对每种分割计算三个组件的异或值并求极差具体步骤树结构构建使用邻接表存储树结构建立双向边连接DFS预处理为每个节点分配dfn序号深度优先编号计算每个子树的异或和xor数组记录每个子树的大小size数组递归公式xor[i] nums[u] ^ xor[child1] ^ xor[child2] ^ ... size[i] 1 size[child1] size[child2] ...边对枚举与处理枚举所有边对组合i,j对每对边 a) 确定两条边对应的dfn区间 b) 判断三种分割情况边j在边i的子树内边j在边i的子树外 c) 计算三个组件的异或值分数计算对每种分割情况计算三个异或值sum1, sum2, sum3求极差max(sum1,sum2,sum3) - min(sum1,sum2,sum3)维护最小极差关键点说明dfn序的应用将树结构线性化通过dfn比较快速判断子树包含关系异或和性质利用异或的自反性A^A0子树异或和的高效计算分割情况判断通过dfn和size确定子树范围区分边在子树内/外的不同处理复杂度分析时间复杂度预处理O(n)DFS遍历边对枚举O(m^2)mn-1为边数总计O(n m^2)空间复杂度O(n)存储dfn、xor、size等数组示例假设树结构0(1) / \ 1(2) 2(3) / \ 3(4) 4(5)括号内为节点值预处理结果dfn [1,2,3,4,5] 索引为节点编号xor [3,6,3,4,5] dfn序号的异或和size [5,3,1,1,1] 子树大小边对处理示例边(0,1)和(1,3)边(0,1) dfn2边(1,3) dfn4判断4在2的子树内2 4 23计算sum1 xor 5sum2 xor^xor 6^5 3sum3 xor^xor 3^6 5极差max(5,3,5)-min(5,3,5)2总结适用场景树形结构的分割优化问题算法优势通过预处理实现高效查询巧妙利用dfn序处理子树关系异或性质简化计算扩展性可应用于其他基于子树分割的问题该算法展示了如何通过树形结构的线性化预处理将复杂的树操作问题转化为高效的数值计算问题是树形数据结构处理的经典范例。代码实现import java.util.ArrayList; import java.util.Arrays; // 从树中删除边的最小分数 // 存在一棵无向连通树树中有编号从0到n-1的n个节点以及n-1条边 // 给你一个下标从0开始的整数数组nums长度为n其中nums[i]表示第i个节点的值 // 另给你一个二维整数数组edges长度为n-1 // 其中 edges[i] [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边 // 删除树中两条不同的边以形成三个连通组件对于一种删除边方案定义如下步骤以计算其分数 // 分别获取三个组件每个组件中所有节点值的异或值 // 最大 异或值和 最小 异或值的 差值 就是这种删除边方案的分数 // 返回可能的最小分数 // 测试链接 : https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/ public class Code04_MinimumScoreAfterRemovals { public static int MAXN 1001; // 下标为原始节点编号 public static int[] dfn new int[MAXN]; // 下标为dfn序号 public static int[] xor new int[MAXN]; // 下标为dfn序号 public static int[] size new int[MAXN]; public static int dfnCnt; public static int minimumScore(int[] nums, int[][] edges) { int n nums.length; ArrayListArrayListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int[] edge : edges) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } Arrays.fill(dfn, 0, n, 0); dfnCnt 0; f(nums, graph, 0); int m edges.length; int ans Integer.MAX_VALUE; for (int i 0, a, b, pre, pos, sum1, sum2, sum3; i m; i) { a Math.max(dfn[edges[i][0]], dfn[edges[i][1]]); for (int j i 1; j m; j) { b Math.max(dfn[edges[j][0]], dfn[edges[j][1]]); if (a b) { pre a; pos b; } else { pre b; pos a; } sum1 xor[pos]; // xor[1] : 整棵树的异或和 // 因为头节点是0一定拥有最小的dfn序号1 // f函数调用的时候也是从0节点开始的 if (pos pre size[pre]) { sum2 xor[pre] ^ xor[pos]; sum3 xor[1] ^ xor[pre]; } else { sum2 xor[pre]; sum3 xor[1] ^ sum1 ^ sum2; } ans Math.min(ans, Math.max(Math.max(sum1, sum2), sum3) - Math.min(Math.min(sum1, sum2), sum3)); } } return ans; } // 当前来到原始编号u遍历u的整棵树 public static void f(int[] nums, ArrayListArrayListInteger graph, int u) { int i dfnCnt; dfn[u] i; xor[i] nums[u]; size[i] 1; for (int v : graph.get(u)) { if (dfn[v] 0) { f(nums, graph, v); xor[i] ^ xor[dfn[v]]; size[i] size[dfn[v]]; } } } }五.选课普通解法邻接表建图 相对好懂的动态规划题目P2014 [CTSC1997] 选课算法原理问题描述给定N门课程每门课程有学分和先修课要求形成森林结构。学生需要选择M门课程要求若选择某课程则必须先修完其先修课程。求能获得的最大学分。整体原理采用树形动态规划DP方法将森林转换为以虚拟根节点连接的树通过后序遍历递归计算各子树在不同选择数量下的最优解。具体步骤建图处理添加虚拟根节点0连接所有无先修课的课程使用邻接表存储树结构graph动态规划定义dp[i][j][k]以i为根的子树在前j个子树中选择k门课的最大学分初始化所有值为-1表示未计算递归函数设计基本情况k0时返回0不选任何课j0或k1时只能选当前课程状态转移不选第j棵子树f(i,j-1,k)选第j棵子树的s门课f(i,j-1,k-s) f(v,child_size,s)记忆化存储计算结果结果计算从虚拟根节点启动递归返回f(0, child_size, m)作为最终结果关键点说明虚拟根节点将森林统一为树结构方便统一处理无先修课的课程三维DP设计第一维当前节点第二维考虑的子节点范围第三维剩余可选课程数转移方程体现选课必须选先修课的约束通过子树组合计算最优解复杂度分析时间复杂度O(N*M²)每个节点处理M次每次处理最多M种分割方式空间复杂度O(N*M)三维DP表存储中间结果示例假设课程关系虚拟0├─1(学分2)├─2(学分3)│ └─3(学分1)└─4(学分4)选择3门课的处理过程节点3只能选自己节点2不选子树选自己得3选子树235选2和3最终在虚拟根计算最优组合总结适用场景树形依赖的选择优化问题算法优势正确处理先修课约束记忆化避免重复计算教学价值展示树形DP的经典应用演示森林转树的处理技巧该算法通过系统的状态设计和记忆化搜索高效解决了课程选择这一经典树形依赖优化问题。代码实现// 选课 // 在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习 // 在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习 // 现在有 N 门功课每门课有个学分每门课有一门或没有直接先修课 // 若课程 a 是课程 b 的先修课即只有学完了课程 a才能学习课程 b // 一个学生要从这些课程里选择 M 门课程学习 // 问他能获得的最大学分是多少 // 测试链接 : https://www.luogu.com.cn/problem/P2014 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的code提交时请把类名改成Main可以直接通过 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.ArrayList; // 普通解法邻接表建图 相对好懂的动态规划 // 几乎所有题解都是普通解法的思路只不过优化了常数时间、做了空间压缩 // 但时间复杂度依然是O(n * 每个节点的孩子平均数量 * m的平方) public class Code05_CourseSelection1 { public static int MAXN 301; public static int[] nums new int[MAXN]; public static ArrayListArrayListInteger graph; static { graph new ArrayList(); for (int i 0; i MAXN; i) { graph.add(new ArrayList()); } } public static int[][][] dp new int[MAXN][][]; public static int n, m; public static void build(int n) { for (int i 0; i n; i) { graph.get(i).clear(); } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in new StreamTokenizer(br); PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); while (in.nextToken() ! StreamTokenizer.TT_EOF) { // 节点编号从0~n n (int) in.nval; in.nextToken(); m (int) in.nval 1; build(n); for (int i 1, pre; i n; i) { in.nextToken(); pre (int) in.nval; graph.get(pre).add(i); in.nextToken(); nums[i] (int) in.nval; } out.println(compute()); } out.flush(); out.close(); br.close(); } public static int compute() { for (int i 0; i n; i) { dp[i] new int[graph.get(i).size() 1][m 1]; } for (int i 0; i n; i) { for (int j 0; j dp[i].length; j) { for (int k 0; k m; k) { dp[i][j][k] -1; } } } return f(0, graph.get(0).size(), m); } // 当前来到i号节点为头的子树 // 只在i号节点、及其i号节点下方的前j棵子树上挑选节点 // 一共挑选k个节点并且保证挑选的节点连成一片 // 返回最大的累加和 public static int f(int i, int j, int k) { if (k 0) { return 0; } if (j 0 || k 1) { return nums[i]; } if (dp[i][j][k] ! -1) { return dp[i][j][k]; } int ans f(i, j - 1, k); // 第j棵子树头节点v int v graph.get(i).get(j - 1); for (int s 1; s k; s) { ans Math.max(ans, f(i, j - 1, k - s) f(v, graph.get(v).size(), s)); } dp[i][j][k] ans; return ans; } }六.选课最优解链式前向星建图 dfn序的利用 巧妙定义下的尝试题目P2014 [CTSC1997] 选课算法原理问题描述给定N门课程及其先修关系形成森林结构每门课程有对应学分。要求选择M门课程且选择某课程必须先修完其先修课程。求能获得的最大学分。整体原理采用链式前向星建图DFN序处理动态规划的最优解法通过树形线性化和逆向DP计算将时间复杂度优化至O(N*M)。具体步骤树形结构预处理使用链式前向星存储树结构添加虚拟根节点0连接所有无先修课的课程进行DFS遍历为每个节点分配DFN序号记录每个节点的子树大小(size)和学分(val)动态规划定义dp[i][j]从DFN序i到n1的节点中选择j个形成有效结构的最大学分有效结构定义选择的节点在树形结构上是连续的逆向DP计算按DFN序从大到小处理状态转移方程不选当前节点dp[i][j] dp[isize[i]][j]选当前节点dp[i][j] val[i] dp[i1][j-1]取两种选择的最大值结果计算最终结果为虚拟根节点学分加上dp[m]保证整体选择的课程数恰好为M门关键创新点DFN序的巧妙应用将树形结构转化为线性序列通过DFN序保证子树节点连续存储逆向DP设计从叶子节点向根节点计算利用size数组快速跳过子树范围有效结构定义确保选择的课程集合在树形结构上连通自然满足先修课程约束条件复杂度分析时间复杂度O(N*M)DFS预处理O(N)DP计算O(N*M)空间复杂度O(N*M)存储DP表示例假设课程关系虚拟0(学分0)├─1(2)├─2(3)│ └─3(1)└─4(4)DFN序分配1:0, 2:1, 3:2, 4:3, 5:4DP计算过程m3处理节点5只能选自己处理节点4选4得4分处理节点3选3得1分处理节点2不选继承节点4的结果选3 节点3的结果最终组合选2、3、4得8分总结效率提升相比传统树形DP的O(NM²)优化到O(NM)避免重复计算子树信息实现简洁通过DFN序简化树形结构处理状态转移方程清晰明确扩展性强可应用于其他树形依赖的选择问题方法可推广到更复杂的约束条件该算法通过创新的线性化处理和逆向动态规划完美解决了课程选择这一经典问题展示了算法设计中对问题本质的深刻理解和巧妙转化。代码实现// 选课 // 在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习 // 在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习 // 现在有 N 门功课每门课有个学分每门课有一门或没有直接先修课 // 若课程 a 是课程 b 的先修课即只有学完了课程 a才能学习课程 b // 一个学生要从这些课程里选择 M 门课程学习 // 问他能获得的最大学分是多少 // 测试链接 : https://www.luogu.com.cn/problem/P2014 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的code提交时请把类名改成Main可以直接通过 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Arrays; // 最优解链式前向星建图 dfn序的利用 巧妙定义下的尝试 // 时间复杂度O(n*m)觉得难可以跳过这个最优解是非常巧妙和精彩的 public class Code05_CourseSelection2 { public static int MAXN 301; public static int[] nums new int[MAXN]; // 链式前向星建图 public static int edgeCnt; public static int[] head new int[MAXN]; public static int[] next new int[MAXN]; public static int[] to new int[MAXN]; // dfn的计数 public static int dfnCnt; // 下标为dfn序号 public static int[] val new int[MAXN 1]; // 下标为dfn序号 public static int[] size new int[MAXN 1]; // 动态规划表 public static int[][] dp new int[MAXN 2][MAXN]; public static int n, m; public static void build(int n, int m) { edgeCnt 1; dfnCnt 0; Arrays.fill(head, 0, n 1, 0); Arrays.fill(dp[n 2], 0, m 1, 0); } public static void addEdge(int u, int v) { next[edgeCnt] head[u]; to[edgeCnt] v; head[u] edgeCnt; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in new StreamTokenizer(br); PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); while (in.nextToken() ! StreamTokenizer.TT_EOF) { n (int) in.nval; in.nextToken(); m (int) in.nval; build(n, m); for (int i 1; i n; i) { in.nextToken(); addEdge((int) in.nval, i); in.nextToken(); nums[i] (int) in.nval; } out.println(compute()); } out.flush(); out.close(); br.close(); } public static int compute() { f(0); // 节点编号0 ~ ndfn序号范围1 ~ n1 // 接下来的逻辑其实就是01背包不过经历了很多转化 // 整体的顺序是根据dfn序来进行的从大的dfn序遍历到小的dfn序 // dp[i][j] : i ~ n1 范围的节点选择j个节点一定要形成有效结构的情况下最大的累加和 // 怎么定义有效结构重点重点重点 // 假设i ~ n1范围上目前所有头节点的上方有一个总的头节点 // i ~ n1范围所有节点选出来j个节点的结构 // 挂在这个假想的总头节点之下是一个连续的结构没有断开的情况 // 那么就说i ~ n1范围所有节点选出来j个节点的结构是一个有效结构 for (int i n 1; i 2; i--) { for (int j 1; j m; j) { dp[i][j] Math.max(dp[i size[i]][j], val[i] dp[i 1][j - 1]); } } // dp[2][m] : 2 ~ n范围上选择m个节点一定要形成有效结构的情况下最大的累加和 // 最后来到dfn序为1的节点一定是原始的0号节点 // 原始0号节点下方一定挂着有效结构 // 并且和补充的0号节点一定能整体连在一起没有任何跳跃连接 // 于是整个问题解决 return nums[0] dp[2][m]; } // u这棵子树的节点数返回 public static int f(int u) { int i dfnCnt; val[i] nums[u]; size[i] 1; for (int ei head[u], v; ei 0; ei next[ei]) { v to[ei]; size[i] f(v); } return size[i]; } }