• Leetcode 3562. Maximum Profit from Trading Stocks with Discounts
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3562. Maximum Profit from Trading Stocks with Discounts

1. 解題思路

這一題沒有搞定，思路上整體走偏了，看了一下別人的解答，結合deepseek的回答看了半天，終于是搞明白了里面的道道，也是醉了……

這一題我自己的思路就是一個遍歷，分別考察每一個用戶買與不買的情況下budget的變化以及對其下屬員工price的變動，但是遇到了超時的問題。

然后deepseek給到的解答是視為一個背包問題，即不是考察每個員工買不不買的情況，而是考察給每一個員工及其下屬員工分配多少的預算，然后看其最大能獲得多大的利潤。即，給到的最終的動態規劃的數組為dp[uid][status][budget]，其中，uid表示用戶id；status表示其父節點的購買狀態，即直屬上司是否有購買行為；budget表示給該用戶及其下屬所有員工分配的budget；然后dp[uid][status][budget]整體表示當uid用戶的直屬上司的購買狀態為status時，給他及其下屬所有員工分配budget預算時，能夠獲得的最大的profit。

由此一來，我們就可以使用動態規劃進行處理了。

2. 代碼實現

給出python代碼實現如下：

class Solution:def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:tree = defaultdict(list)for u, v in hierarchy:tree[u - 1].append(v - 1)@lru_cache(None)def dp(u):'''input: u : int -> 0-based user idoutput: - dp0: [int] * (budget+1) -> max profit for each budget if parent node was not bought- dp1: [int] * (budget+1) -> max profit for each budget if parent node was bought'''child_dp = [dp(v) for v in tree[u]]dp0 = [0] * (budget+1) # parent not buydp1 = [0] * (budget+1) # parent buyfor parent_bought, max_profits in [(0, dp0), (1, dp1)]:cost = present[u] if parent_bought == 0 else present[u] // 2profit = future[u] - costdpA = [0] + [-math.inf] * (budget) # u not buydpB = [-math.inf] * (budget+1) # u buyif cost <= budget:dpB[cost] = profitfor case0, case1 in child_dp:new_dpA = [-math.inf] * (budget+1) # u not buyfor bgt in range(budget+1):if dpA[bgt] == -math.inf:continuefor k in range(budget-bgt+1):if case0[k] == -math.inf:continuenew_dpA[bgt+k] = max(new_dpA[bgt+k], dpA[bgt] + case0[k])dpA = new_dpAnew_dpB = [-math.inf] * (budget+1) # u buyfor bgt in range(budget+1):if dpB[bgt] == -math.inf:continuefor k in range(budget-bgt+1):if case1[k] == -math.inf:continuenew_dpB[bgt+k] = max(new_dpB[bgt+k], dpB[bgt] + case1[k])dpB = new_dpBfor bgt in range(budget+1):max_profits[bgt] = max(dpA[bgt], dpB[bgt])return dp0, dp1max_profits, _ = dp(0)return max(max_profits)

提交代碼評測得到：耗時2362ms，占用內存22.8MB。