建站建设流程,网站建设运行环境,大连企业招聘网站,泰安网站建设公司Leetcode 3562. Maximum Profit from Trading Stocks with Discounts 1. 解题思路2. 代码实现 题目链接#xff1a;3562. Maximum Profit from Trading Stocks with Discounts
1. 解题思路
这一题没有搞定#xff0c;思路上整体走偏了#xff0c;看了一下别人的解答…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表示用户idstatus表示其父节点的购买状态即直属上司是否有购买行为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] * (budget1) - max profit for each budget if parent node was not bought- dp1: [int] * (budget1) - max profit for each budget if parent node was boughtchild_dp [dp(v) for v in tree[u]]dp0 [0] * (budget1) # parent not buydp1 [0] * (budget1) # 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] * (budget1) # u buyif cost budget:dpB[cost] profitfor case0, case1 in child_dp:new_dpA [-math.inf] * (budget1) # u not buyfor bgt in range(budget1):if dpA[bgt] -math.inf:continuefor k in range(budget-bgt1):if case0[k] -math.inf:continuenew_dpA[bgtk] max(new_dpA[bgtk], dpA[bgt] case0[k])dpA new_dpAnew_dpB [-math.inf] * (budget1) # u buyfor bgt in range(budget1):if dpB[bgt] -math.inf:continuefor k in range(budget-bgt1):if case1[k] -math.inf:continuenew_dpB[bgtk] max(new_dpB[bgtk], dpB[bgt] case1[k])dpB new_dpBfor bgt in range(budget1):max_profits[bgt] max(dpA[bgt], dpB[bgt])return dp0, dp1max_profits, _ dp(0)return max(max_profits)提交代码评测得到耗时2362ms占用内存22.8MB。
