Leetcode 3186. Maximum Total Damage With Spell Casting

本文主要是介绍Leetcode 3186. Maximum Total Damage With Spell Casting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 3186. Maximum Total Damage With Spell Casting
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3186. Maximum Total Damage With Spell Casting

1. 解题思路

这一题就是一个简单的动态规划的题目，我们只需要考虑每一个位置上的元素取或者不取即可：

• 如果不取，直接考察下一个元素即可；
• 如果取，考察能够获得的damage的值加上下一个可行的位置上进行考察即可。

2. 代码实现

给出python代码实现如下：

class Solution:def maximumTotalDamage(self, power: List[int]) -> int:power = sorted(Counter(power).items())n = len(power)@lru_cache(None)def dp(idx):if idx >= n:return 0nxt = idxwhile nxt < n and power[nxt][0] <= power[idx][0]+2:nxt += 1return max(dp(idx+1), power[idx][0] * power[idx][1] + dp(nxt))return dp(0)

提交代码评测得到：耗时1849ms，占用内存249.1MB。

这篇关于Leetcode 3186. Maximum Total Damage With Spell Casting的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---