Kimi LeetCode 3562. 折扣价交易股票的最大利润 Python3实现

LeetCode 3562. 折扣价交易股票的最大利润 — Python3 实现题目概述给定 n 名员工员工 1 是 CEO每人有当前股价 present[i] 和未来股价 future[i]。员工层级关系由 hierarchy 给出[u, v] 表示 u 是 v 的直属上司。预算为 budget。折扣规则若某位员工的直属上司购买了股票则该员工可以 半价present[v] // 2购买。目标在不超过预算的前提下获得最大利润。解题思路树形 DP 01 背包对每个节点 u维护两个一维 DP 数组- dp0[b]在 u 的子树中预算不超过 b且 u 的父节点未买时的最大利润- dp1[b]在 u 的子树中预算不超过 b且 u 的父节点已买时的最大利润核心步骤1. 构建树将层级关系转为邻接表0-based 索引2. 后序 DFS先处理子节点再处理当前节点3. 合并子树01 背包将每个子节点的 DP 数组合并到当前节点4. 决定是否购买当前节点- 父节点未买当前节点原价购买子节点看到父节点买了用 dp1- 父节点已买当前节点半价购买子节点看到父节点买了用 dp1Python3 代码pythonimport mathimport functoolsclass Solution:def maxProfit(self,n: int,present: list[int],future: list[int],hierarchy: list[list[int]],budget: int,) - int:# 构建树形邻接表0-based 索引tree [[] for _ in range(n)]for u, v in hierarchy:tree[u - 1].append(v - 1)functools.lru_cache(None)def dp(u: int, parent: int) - tuple[list[int], list[int]]:返回 (dp0, dp1):dp0[b]: 父节点未买时子树u预算b的最大利润dp1[b]: 父节点已买时子树u预算b的最大利润# 初始化不买任何子节点利润为0noDiscount [0] * (budget 1) # 父节点未买 → 子节点也未看到父买withDiscount [0] * (budget 1) # 父节点已买 → 子节点看到父买# 遍历每个子节点用01背包合并for v in tree[u]:if v parent:continuechildNoDiscount, childWithDiscount dp(v, u)noDiscount self._merge(noDiscount, childNoDiscount)withDiscount self._merge(withDiscount, childWithDiscount)# 复制一份准备考虑买当前节点u的情况newDp0 noDiscount[:] # 父节点未买时的最终状态newDp1 noDiscount[:] # 父节点已买时的最终状态注意子树合并基础相同# 情况1父节点未买当前节点u按原价购买fullCost present[u]profitFull future[u] - fullCostfor b in range(fullCost, budget 1):# 买了u子节点v看到父节点买了所以用 withDiscountnewDp0[b] max(newDp0[b], withDiscount[b - fullCost] profitFull)# 情况2父节点已买当前节点u按半价购买halfCost present[u] // 2profitHalf future[u] - halfCostfor b in range(halfCost, budget 1):# 买了u子节点v看到父节点买了所以用 withDiscountnewDp1[b] max(newDp1[b], withDiscount[b - halfCost] profitHalf)return newDp0, newDp1# 从根节点(CEO, 索引0)开始父节点视为-1(不存在)取dp0状态根无父节点视为未买return max(dp(0, -1)[0])def _merge(self, dpA: list[int], dpB: list[int]) - list[int]:01背包合并两个子树的DP数组dpA: 已合并的子树状态dpB: 待合并的新子树状态merged [-math.inf] * len(dpA)for i, a in enumerate(dpA):for j in range(len(dpA) - i):merged[i j] max(merged[i j], a dpB[j])return merged复杂度分析指标 复杂度时间 O(n \times \text{budget}^2) — 对每个节点做背包合并空间 O(n \times \text{budget}) — 递归栈 DP 数组 LRU Cache关键细节说明1. 索引转换题目中员工 ID 是 1-based代码中转为 0-basedtree[u - 1].append(v - 1)。2. 状态定义- noDiscount / newDp0父节点未买时当前节点按原价购买子节点看到父买了用 withDiscount 合并- withDiscount / newDp1父节点已买时当前节点按半价购买子节点看到父买了用 withDiscount 合并3. 合并逻辑_merge 函数实现 01 背包将两个子树的预算分配方案组合取最大利润。4. LRU Cachefunctools.lru_cache(None) 缓存每个节点的 DP 结果避免重复计算。该解法参考了 walkccc.me 的 Python 题解 的实现思路。