Solution

Method 1 – Dynamic Programming with Frequency Counting

Intuition

This problem is similar to the "House Robber" or "Delete and Earn" pattern, but with a wider forbidden range. For each unique damage value, if we cast spells of this damage, we must skip all spells with damage within 2 of it. We use dynamic programming to track the best total damage at each value.

Approach

Count the frequency of each damage value in power.
Sort the unique damage values.
Use a DP array where dp[i] is the max damage using up to the ith unique value:
- For each value, either:
  - Skip it: take dp[i-1].
  - Take it: add its total damage to dp[j], where j is the last index with value at least 3 less than current.
Return the last value in the DP array.

Related Tags