树 形 DP (dnf序)

题目1333. 最大二叉搜索子树 - 力扣LeetCode// 最大BST子树 // 给定一个二叉树找到其中最大的二叉搜索树BST子树并返回该子树的大小 // 其中最大指的是子树节点数最多的 // 二叉搜索树BST中的所有节点都具备以下属性 // 左子树的值小于其父根节点的值 // 右子树的值大于其父根节点的值 // 注意子树必须包含其所有后代 // 测试链接 : https://leetcode.cn/problems/largest-bst-subtree/ public class Code01_LargestBstSubtree { // 不要提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static int largestBSTSubtree(TreeNode root) { return f(root).maxBstSize; } public static class Info { public long max; public long min; public boolean isBst; public int maxBstSize; public Info(long a, long b, boolean c, int d) { max a; min b; isBst c; maxBstSize d; } } public static Info f(TreeNode x) { if (x null) { return new Info(Long.MIN_VALUE, Long.MAX_VALUE, true, 0); } Info infol f(x.left); Info infor f(x.right); // 左 4信息 // 右 4信息 // x 整合出4信息返回 long max Math.max(x.val, Math.max(infol.max, infor.max)); long min Math.min(x.val, Math.min(infol.min, infor.min)); boolean isBst infol.isBst infor.isBst infol.max x.val x.val infor.min; int maxBSTSize; if (isBst) { maxBSTSize infol.maxBstSize infor.maxBstSize 1; } else { maxBSTSize Math.max(infol.maxBstSize, infor.maxBstSize); } return new Info(max, min, isBst, maxBSTSize); } }题目2递归求从头节点向下的最大的最大子树键值和而到一个头节点要求其最大的键值和如果不选头节点需要子树上的最大键值和如果选头节点需要知道子树是否为二叉搜索树和子树所有节点的和并且还需要子树上的最大值和最小值和头节点比较判断是否可以选头节点。最后把所有需要的信息整合到一起传递给父节点二叉搜索子树的最大键值// 二叉搜索子树的最大键值和 // 给你一棵以 root 为根的二叉树 // 请你返回 任意 二叉搜索子树的最大键值和 // 二叉搜索树的定义如下 // 任意节点的左子树中的键值都 小于 此节点的键值 // 任意节点的右子树中的键值都 大于 此节点的键值 // 任意节点的左子树和右子树都是二叉搜索树 // 测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/ public class Code02_MaximumSumBst { // 不要提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static int maxSumBST(TreeNode root) { return f(root).maxBstSum; } public static class Info { // 为什么这里的max和min是int类型 // 因为题目的数据量规定 // 节点值在[-4 * 10^44 * 10^4]范围 // 所以int类型的最小值和最大值就够用了 // 不需要用long类型 public int max; public int min; public int sum; public boolean isBst; public int maxBstSum; public Info(int a, int b, int c, boolean d, int e) { max a; min b; sum c; isBst d; maxBstSum e; } } public static Info f(TreeNode x) { if (x null) {//空节点的最大maxBSTSum设置为0是因为题目要求可以不选节点 return new Info(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, true, 0); } Info infol f(x.left); Info infor f(x.right); int max Math.max(x.val, Math.max(infol.max, infor.max)); int min Math.min(x.val, Math.min(infol.min, infor.min)); int sum infol.sum infor.sum x.val; boolean isBst infol.isBst infor.isBst infol.max x.val x.val infor.min; int maxBstSum Math.max(infol.maxBstSum, infor.maxBstSum); if (isBst) { maxBstSum Math.max(maxBstSum, sum); } return new Info(max, min, sum, isBst, maxBstSum); } }题目3从一个头节点及其子树求最大的直径如果不选头节点需要其子树的最大直径和如果选头节点需要子树的高度二叉树的直径// 二叉树的直径 // 给你一棵二叉树的根节点返回该树的直径 // 二叉树的 直径 是指树中任意两个节点之间最长路径的长度 // 这条路径可能经过也可能不经过根节点 root // 两节点之间路径的 长度 由它们之间边数表示 // 测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/ public class Code03_DiameterOfBinaryTree { // 不要提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static int diameterOfBinaryTree(TreeNode root) { return f(root).diameter; } public static class Info { public int diameter; public int height; public Info(int a, int b) { diameter a; height b; } } public static Info f(TreeNode x) { if (x null) { return new Info(0, 0); } Info leftInfo f(x.left); Info rightInfo f(x.right); int height Math.max(leftInfo.height, rightInfo.height) 1; int diameter Math.max(leftInfo.diameter, rightInfo.diameter); diameter Math.max(diameter, leftInfo.height rightInfo.height); return new Info(diameter, height); } }题目4所有硬币的移动路径之和是由每条边经过的次数累加和组成所以只要求出每条边的经过次数求和即可。求一个子树所有边的经过次数之和需要其子树的所有经过边之和还有每个子树的节点与其子树上的硬币数量做差的绝对值就是从头节点的子树到头节点之间的那条边经过的次数在二叉树中分配金币/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */ class Solution { public: int ans 0; int f(TreeNode* root) { if (root nullptr) return 0; int d f(root-left) f(root-right) root-val - 1; ans abs(d); return d; } int distributeCoins(TreeNode* root) { f(root); return ans; } };题目5求一个树的最大快乐值如果不选头节点只需要其子树选子树头节点的最大快乐值和不选子树头节点的最大快乐值如果选头节点需要不选子树头节点的最大快乐值没有上司的舞会// 没有上司的舞会 // 某大学有n个职员编号为1...n // 他们之间有从属关系也就是说他们的关系就像一棵以校长为根的树 // 父结点就是子结点的直接上司 // 现在有个周年庆宴会宴会每邀请来一个职员都会增加一定的快乐指数 // 但是如果某个职员的直接上司来参加舞会了 // 那么这个职员就无论如何也不肯来参加舞会了 // 所以请你编程计算邀请哪些职员可以使快乐指数最大 // 返回最大的快乐指数。 // 测试链接 : https://www.luogu.com.cn/problem/P1352 // 本题和讲解037的题目7类似 // 链式链接 : https://leetcode.cn/problems/house-robber-iii/ // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的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; public class Code05_Dancing { public static int MAXN 6001; public static int[] nums new int[MAXN]; public static boolean[] boss new boolean[MAXN]; // 链式前向星建图 public static int[] head new int[MAXN]; public static int[] next new int[MAXN]; public static int[] to new int[MAXN]; public static int cnt; // 动态规划表 // no[i] : i为头的整棵树在i不来的情况下整棵树能得到的最大快乐值 public static int[] no new int[MAXN]; // no[i] : i为头的整棵树在i来的情况下整棵树能得到的最大快乐值 public static int[] yes new int[MAXN]; public static int n, h; public static void build(int n) { Arrays.fill(boss, 1, n 1, true); Arrays.fill(head, 1, n 1, 0); cnt 1; } public static void addEdge(int u, int v) { next[cnt] head[u]; to[cnt] v; head[u] cnt; } 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; build(n); for (int i 1; i n; i) { in.nextToken(); nums[i] (int) in.nval; } for (int i 1, low, high; i n; i) { in.nextToken(); low (int) in.nval; in.nextToken(); high (int) in.nval; addEdge(high, low); boss[low] false; } for (int i 1; i n; i) { if (boss[i]) { h i; break; } } f(h); out.println(Math.max(no[h], yes[h])); } out.flush(); out.close(); br.close(); } public static void f(int u) { no[u] 0; yes[u] nums[u]; for (int ei head[u], v; ei 0; ei next[ei]) { v to[ei]; f(v); no[u] Math.max(no[v], yes[v]); yes[u] no[v]; } } }题目6一个节点的情况1.没有被监控覆盖 2.被覆盖但没有放监控 3.被覆盖并且放了监控根据不同的节点情况讨论即可监控二叉树// 监控二叉树 // 给定一个二叉树我们在树的节点上安装摄像头 // 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象 // 计算监控树的所有节点所需的最小摄像头数量 // 测试链接 : https://leetcode.cn/problems/binary-tree-cameras/ public class Code06_BinaryTreeCameras { // 不要提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public int minCameraCover(TreeNode root) { ans 0; if (f(root) 0) { ans; } return ans; } // 遍历过程中一旦需要放置相机ans public static int ans; // 递归含义 // 假设x上方一定有父亲的情况下这个假设很重要 // x为头的整棵树最终想都覆盖 // 并且想使用最少的摄像头x应该是什么样的状态 // 返回值含义 // 0: x是无覆盖的状态x下方的节点都已经被覆盖 // 1: x是覆盖状态x上没摄像头x下方的节点都已经被覆盖 // 2: x是覆盖状态x上有摄像头x下方的节点都已经被覆盖 private int f(TreeNode x) { if (x null) { return 1; } int left f(x.left); int right f(x.right); if (left 0 || right 0) { ans; return 2; } if (left 1 right 1) { return 0; } return 1; } }题目7树形dp不仅父亲节点需要子节点信息也可以从父节点向子节点传递信息。求target的路径如果知道之前遍历过的所有的节点之和和之前所有从根节点到遍历过的节点的的路径和的路径个数求出sum-target的路径个数累加即可路径总和/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int ans;; unordered_maplong ,intumap; void f(TreeNode* cur,long sum,int targetSum){ if(curnullptr)return ; sumcur-val; long needsum-targetSum; if(umap.find(need)!nullptr) ansumap[need]; umap[sum]; f(cur-left,sum,targetSum); f(cur-right,sum,targetSum); umap[sum]--; } int pathSum(TreeNode* root, int targetSum) { umap.clear(); ans0; umap[0]1; f(root,0,targetSum); return ans; } };题目8求到达头节点a的最少油量需要其子树的最少油量还需要到达其子树的头节点的人的个数人数对seats求上限加子树的油量就是到达a的最少油量到达首都的最少耗油量public class Solution { public static long minimumFuelCost(int[][] roads, int seats) { int n roads.length 1; ArrayListArrayListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int[] r : roads) { graph.get(r[0]).add(r[1]); graph.get(r[1]).add(r[0]); } int[] size new int[n]; long[] cost new long[n]; f(graph, seats, 0, -1, size, cost); return cost[0]; } // 根据图当前来到uu的父节点是p // 遍历完成后请填好size[u]、cost[u] public static void f(ArrayListArrayListInteger graph, int seats, int u, int p, int[] size, long[] cost) { size[u] 1; for (int v : graph.get(u)) { if (v ! p) { f(graph, seats, v, u, size, cost); size[u] size[v]; cost[u] cost[v]; // a/b向上取整可以写成(ab-1)/b // (size[v]seats-1) / seats size[v] / seats 向上取整 cost[u] (size[v] seats - 1) / seats; } } } }题目9求头节点a的子树的最大路径如果不选a需a的子树的最大路径和如果选a需要子树的头节点向下延申的最大长度相邻字符不同的最长路径class Solution { public: vectorvectorint pragh; void build(int n) { for (int i 0; i n; i) pragh.push_back(vectorint()); } void insert(int u, int v) { pragh[u].push_back(v); } class info { public: int maxhead; int maxleng; info(int a, int b) { maxhead a; maxleng b; } }; info f(string s, int cur) { if (pragh[cur].empty()) return info(1, 1); int max1 0, max2 0; int maxheight 0; for (int edge : pragh[cur]) { info rem f(s, edge); maxheight max(maxheight, rem.maxleng); if (s[cur] ! s[edge]) { if (rem.maxhead max1) { max2 max1; max1 rem.maxhead; } else if (rem.maxhead max2) { max2 rem.maxhead; } } } maxheight max(maxheight, max1 max2 1); int maxn max1 1; return info(maxn, maxheight); } int longestPath(vectorint parent, string s) { int n parent.size(); build(n); for (int i 1; i n; i) { insert(parent[i], i); } return f(s, 0).maxleng; } };题目10对树做dfn序然后求个子树的大小和各节点的深度并且求出dfn数组中每个位置的前缀最大值maxl和后缀最大值maxr然后挨个求就可以移除子树后的二叉树高度/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */ class Solution { public: static const int maxn 100005; int dfn[maxn]; int size[maxn]; int deep[maxn]; int maxl[maxn]; int maxr[maxn]; int dfnnum; void f(TreeNode* cur, int k) { int i dfnnum; dfn[cur-val] i; deep[i] k; size[i] 1; if (cur-left ! nullptr) { f(cur-left, k 1); size[i] size[dfn[cur-left-val]]; } if (cur-right ! nullptr) { f(cur-right, k 1); size[i] size[dfn[cur-right-val]]; } } vectorint treeQueries(TreeNode* root, vectorint queries) { dfnnum 0; f(root, 0); for (int i 1; i dfnnum; i) { maxl[i] max(maxl[i - 1], deep[i]); } maxl[0] 0; maxl[dfnnum 1] 0; for (int i dfnnum; i 1; i--) maxr[i] max(maxr[i 1], deep[i]); maxr[0] 0; maxr[dfnnum 1] 0; int m queries.size(); vectorint ans; 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.push_back(max(leftmax, rightmax)); } return ans; } };题目11求出各子树的异或和然后两次for循环枚举各边从树中删除边的最小分数class Solution { public: static const int maxn 1005; vectorvectorint pragh; int dfn[maxn]; int size[maxn]; int xog[maxn]; int dfnnum; void build(int n) { int dfnnum 0; for (int i 0; i n; i) { pragh.push_back(vectorint()); dfn[i] 0; size[0] 0; xog[i] 0; } } void insert(int u, int v) { pragh[u].push_back(v); pragh[v].push_back(u); } void f(int cur, vectorint nums) { int i dfnnum; dfn[cur] i; xog[i] nums[cur]; size[i] 1; for (auto node : pragh[cur]) { if (dfn[node] 0) { f(node, nums); xog[i] ^ xog[dfn[node]]; size[i] size[dfn[node]]; } } } int minimumScore(vectorint nums, vectorvectorint edges) { int n nums.size(); build(n); for (auto edge : edges) { insert(edge[0], edge[1]); } f(0, nums); int ans INT_MAX; for (int i 0; i edges.size(); i) { int a max(dfn[edges[i][0]], dfn[edges[i][1]]); for (int j i 1; j edges.size(); j) { int b max(dfn[edges[j][0]], dfn[edges[j][1]]); int pre, pos; if (a b) { pre a; pos b; } else { pre b; pos a; } int sum1 xog[pos]; int sum2, sum3; if (pre size[pre] pos) { sum2 sum1 ^ xog[pre]; sum3 xog[pre] ^ xog[1]; } else { sum2 xog[pre]; sum3 sum1 ^ sum2 ^ xog[1]; } ans min(ans, max(sum1, max(sum2, sum3)) - min(sum1, min(sum2, sum3))); } } return ans; } };题目12选课方法1三维树形dp枚举最右子树的分配节点个数讨论// 选课树上01背包的普通解法 // 在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习 // 在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习 // 现在有 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; } }方法21.要 i 号点2.不要 i 号点定义最优子结构从大的dfn序到小的dfn序推出转移方程// 选课树上01背包的最优解 // 在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习 // 在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习 // 现在有 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]; } }