本文主要是介绍Leetcode 2920. Maximum Points After Collecting Coins From All Nodes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- Leetcode 2920. Maximum Points After Collecting Coins From All Nodes
- 1. 解题思路
- 2. 代码实现
- 题目链接：2920. Maximum Points After Collecting Coins From All Nodes
1. 解题思路
这一题思路上也很直接，就是一个深度优先遍历加上一个动态规划，分别考虑在两种情况下对应的coin收集数目，然后取最大值即可。
2. 代码实现
给出python代码实现如下：
class Solution:def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)@lru_cache(None)def dp(u, p, m):if m >= 14:return 0val = coins[u] for _ in range(m):val = val // 2ans = val - kfor v in graph[u]:if v == p:continueans += dp(v, u, m)if val - k < val // 2:ans2 = val // 2for v in graph[u]:if v == p:continueans2 += dp(v, u, m+1)ans = max(ans, ans2)return ansans = dp(0, -1, 0)return ans
提交代码评测得到：耗时3186ms，占用内存424.7MB。
这篇关于Leetcode 2920. Maximum Points After Collecting Coins From All Nodes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
