LeetCode 3562. 折扣价交易股票的最大利润 — Java 实现题目概述给定 n 名员工员工 1 是 CEO每人有当前股价 present[i] 和未来股价 future[i]。员工层级关系由 hierarchy 给出[u, v] 表示 u 是 v 的直属上司。预算为 budget。折扣规则若某位员工的直属上司购买了股票则该员工可以 半价floor(present[v] / 2)购买。目标在不超过预算的前提下获得最大利润。解题思路树形 DP 01 背包对每个节点维护一个二维 DP 数组 f[j][pre]- j预算- pre当前节点的父节点是否购买了股票0未买1已买- f[j][pre]在该子树中预算不超过 j 且父节点购买状态为 pre 时的最大利润核心步骤1. 构建树将层级关系转为邻接表2. 后序 DFS先处理子节点再处理当前节点3. 合并子树01 背包将每个子节点的 DP 数组合并到当前节点4. 决定是否购买当前节点根据父节点状态计算成本 cost present[u] / (pre 1)Java 代码javaimport java.util.*;class Solution {public int maxProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) {// 构建树形邻接表1-based 索引ListInteger[] g new ArrayList[n 1];for (int i 0; i n; i) {g[i] new ArrayList();}for (int[] e : hierarchy) {g[e[0]].add(e[1]);}// 从根节点 1 开始 DFS返回根节点在 budget 预算、父节点未买0时的最大利润int[][] res dfs(1, g, present, future, budget);return res[budget][0];}/*** 返回以 u 为根的子树的 DP 数组* f[j][pre]: 预算为 ju 的父节点购买状态为 pre 时的最大利润* pre 0: 父节点未买pre 1: 父节点已买*/private int[][] dfs(int u, ListInteger[] g, int[] present, int[] future, int budget) {// subF[j][pre]: 合并所有子节点后的状态u 自身尚未决定是否购买int[][] subF new int[budget 1][2];// 遍历每个子节点用 01 背包合并for (int v : g[u]) {int[][] fv dfs(v, g, present, future, budget);// 逆序遍历预算01 背包防止重复选择for (int j budget; j 0; j--) {for (int jv 0; jv j; jv) {for (int pre 0; pre 2; pre) {subF[j][pre] Math.max(subF[j][pre], subF[j - jv][pre] fv[jv][pre]);}}}}// f[j][pre]: 最终状态已考虑 u 自身是否购买int[][] f new int[budget 1][2];// present 和 future 是 0-based 数组员工 u 对应索引 u-1int price future[u - 1];for (int j 0; j budget; j) {for (int pre 0; pre 2; pre) {// 成本若父节点买了(pre1)则半价否则原价int cost present[u - 1] / (pre 1);if (j cost) {// 不买 u利润为 subF[j][0]子节点看不到 u 买所以父状态为 0// 买 u利润为 subF[j-cost][1] (future[u] - cost)子节点看到 u 买了所以父状态为 1int buyProfit subF[j - cost][1] (price - cost);f[j][pre] Math.max(subF[j][0], buyProfit);} else {// 预算不够只能不买f[j][pre] subF[j][0];}}}return f;}}复杂度分析指标 复杂度时间 O(n \times \text{budget}^2) — 对每个节点做背包合并空间 O(n \times \text{budget}) — 递归栈 DP 数组关键细节说明1. 索引转换题目中员工 ID 是 1-basedpresent/future 数组也是 1-based 索引所以访问时用 present[u - 1]。2. 成本计算cost present[u - 1] / (pre 1)- pre 0父节点未买cost present / 1 原价- pre 1父节点已买cost present / 2 半价整数除法自动下取整3. 状态转移- 不买当前节点 u子节点的父状态视为 0用 subF[j][0]- 买当前节点 u子节点的父状态视为 1用 subF[j - cost][1]并加上当前利润 future[u] - cost4. 01 背包逆序合并子节点时预算 j 从大到小遍历避免同一子树被重复选择。该解法参考了 doocs/leetcode 社区题解 的实现思路。