3562. 股票交易折扣的最大利润

Hard

题目描述

给定一个整数 n，表示公司中员工的数量。每个员工都分配了一个从 1 到 n 的唯一 ID，员工 1 是 CEO，是每个员工的直接或间接老板。给定两个基于 1 的整数数组 present 和 future，长度都为 n，其中：

present[i] 表示第 i 个员工今天可以购买股票的当前价格。
future[i] 表示第 i 个员工明天可以卖出股票的预期价格。

公司的层次结构由二维整数数组 hierarchy 表示，其中 hierarchy[i] = [ui, vi] 表示员工 ui 是员工 vi 的直接老板。

此外，你有一个整数 budget 表示可用于投资的总资金。

但是，公司有一个折扣政策：如果员工的直接老板购买了他们自己的股票，那么该员工可以以原价的一半购买他们的股票（floor(present[v] / 2)）。

返回在不超过给定预算的情况下可以实现的最大利润。

注意：

每只股票最多只能买一次。
您不能使用从未来股价中获得的任何利润来资助额外的投资，必须仅从预算中购买。

示例 1：

输入：n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
输出：5

示例 2：

输入：n = 2, present = [3,4], future = [5,8], hierarchy = [[1,2]], budget = 4
输出：4

示例 3：

输入：n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10
输出：10

约束条件：

1 <= n <= 160
present.length, future.length == n
1 <= present[i], future[i] <= 50
hierarchy.length == n - 1
1 <= budget <= 160

解题思路

这是一道树形 DP 问题，核心在于处理员工购买股票时的折扣依赖关系。

解题思路：

构建树结构：根据 hierarchy 构建员工的上下级关系树，CEO（员工1）为根节点。
状态定义：对每个节点 u，定义两种状态：
- dp[u][0][cost]：在子树 u 中，u 的父节点未购买股票时，花费 cost 能获得的最大利润
- dp[u][1][cost]：在子树 u 中，u 的父节点已购买股票时，花费 cost 能获得的最大利润
状态转移：对于每个节点，考虑两种选择：
- 购买当前员工的股票：根据父节点是否购买确定价格（原价或半价），然后递归处理子节点
- 不购买当前员工的股票：直接处理子节点，父节点状态不变
优化技巧：由于预算和价格范围都较小，可以使用三维 DP 数组，通过记忆化搜索避免重复计算。

算法步骤：

构建邻接表表示树结构
从根节点开始进行 DFS + DP
对每个节点尝试购买和不购买两种情况
合并子节点的最优结果
返回根节点在预算内的最大利润

代码实现

class Solution {
public:
    int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
        vector<vector<int>> children(n + 1);
        for (auto& edge : hierarchy) {
            children[edge[0]].push_back(edge[1]);
        }
        
        // memo[node][parent_bought][cost] = max_profit
        vector<vector<vector<int>>> memo(n + 1, vector<vector<int>>(2, vector<int>(budget + 1, -1)));
        
        function<int(int, bool, int)> dfs = [&](int node, bool parent_bought, int remaining) -> int {
            if (remaining < 0) return -1e9;
            if (memo[node][parent_bought][remaining] != -1) {
                return memo[node][parent_bought][remaining];
            }
            
            int result = 0;
            
            // Option 1: Don't buy stock for current node
            for (int child : children[node]) {
                result += dfs(child, false, remaining);
            }
            
            // Option 2: Buy stock for current node
            int cost = parent_bought ? present[node - 1] / 2 : present[node - 1];
            if (remaining >= cost) {
                int profit = future[node - 1] - cost;
                int child_profit = 0;
                int child_remaining = remaining - cost;
                
                for (int child : children[node]) {
                    child_profit += dfs(child, true, child_remaining);
                }
                
                result = max(result, profit + child_profit);
            }
            
            return memo[node][parent_bought][remaining] = result;
        };
        
        return dfs(1, false, budget);
    }
};

class Solution:
    def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
        children = [[] for _ in range(n + 1)]
        for u, v in hierarchy:
            children[u].append(v)
        
        from functools import lru_cache
        
        @lru_cache(None)
        def dfs(node, parent_bought, remaining):
            if remaining < 0:
                return float('-inf')
            
            # Option 1: Don't buy stock for current node
            result = 0
            for child in children[node]:
                result += dfs(child, False, remaining)
            
            # Option 2: Buy stock for current node
            cost = present[node - 1] // 2 if parent_bought else present[node - 1]
            if remaining >= cost:
                profit = future[node - 1] - cost
                child_profit = 0
                child_remaining = remaining - cost
                
                for child in children[node]:
                    child_profit += dfs(child, True, child_remaining)
                
                result = max(result, profit + child_profit)
            
            return result
        
        return dfs(1, False, budget)

public class Solution {
    public int MaxProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) {
        var children = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            children[i] = new List<int>();
        }
        
        foreach (var edge in hierarchy) {
            children[edge[0]].Add(edge[1]);
        }
        
        var memo = new Dictionary<(int, bool, int), int>();
        
        int Dfs(int node, bool parentBought, int remaining) {
            if (remaining < 0) return int.MinValue / 2;
            
            var key = (node, parentBought, remaining);
            if (memo.ContainsKey(key)) {
                return memo[key];
            }
            
            // Option 1: Don't buy stock for current node
            int result = 0;
            foreach (int child in children[node]) {
                result += Dfs(child, false, remaining);
            }
            
            // Option 2: Buy stock for current node
            int cost = parentBought ? present[node - 1] / 2 : present[node - 1];
            if (remaining >= cost) {
                int profit = future[node - 1] - cost;
                int childProfit = 0;
                int childRemaining = remaining - cost;
                
                foreach (int child in children[node]) {
                    childProfit += Dfs(child, true, childRemaining);
                }
                
                result = Math.Max(result, profit + childProfit);
            }
            
            memo[key] = result;
            return result;
        }
        
        return Dfs(1, false, budget);
    }
}

var maxProfit = function(n, present, future, hierarchy, budget) {
    const children = Array(n + 1).fill().map(() => []);
    for (const [u, v] of hierarchy) {
        children[u].push(v);
    }
    
    const memo = new Map();
    
    function dfs(node, parentBought, remaining) {
        if (remaining < 0) return -Infinity;
        
        const key = `${node},${parentBought},${remaining}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        // Option 1: Don't buy stock for current node
        let result = 0;
        for (const child of children[node]) {
            result += dfs(child, false, remaining);
        }
        
        // Option 2: Buy stock for current node
        const cost = parentBought ? Math.floor(present[node - 1] / 2) : present[node - 1];
        if (remaining >= cost) {
            const profit = future[node - 1] - cost;
            let childProfit = 0;
            const childRemaining = remaining - cost;
            
            for (const child of children[node]) {
                childProfit += dfs(child, true, childRemaining);
            }
            
            result = Math.max(result, profit + childProfit);
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dfs(1, false, budget);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小
时间复杂度	O(n × budget × 2)
空间复杂度	O(n × budget × 2)

时间复杂度：每个节点有两种父节点状态（购买/未购买），预算范围为 0 到 budget，总共 O(n × budget × 2) 个状态需要计算。

空间复杂度：记忆化搜索需要存储所有可能的状态，加上递归调用栈的深度 O(n)。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析