难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1:

输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。

示例 2:

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
注意:

nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。

解答

这个题是穿了马夹的《打家劫舍》问题。为什么这么讲，当取了一个数字，相邻数字都不可以取，不是和打家劫舍问题中打劫了一家，相邻家户不可以打劫是一样的道理吗。

认识了这实际上是一道打家劫舍问题，问题就在于，怎么样把这种数值的关系，转换成像打家劫舍一样位置的关系。我们采取的策略是，建立数值对下标的映射。例如数组[1,1,1,1,3,3]中，有4个1和2个3，我们希望建立的数组是按照数值-位置映射后的每个元素的和，即[1+1+1+1, 0, 3+3]。

因此，我们可以通过统计每个元素出现的次数，建立每家每户的财富列表treasure（可能是包含很多零的数组），剩下的就可以使用打家劫舍的动态规划来做了。这里回顾一下动态规划的过程：

【定义数组】数组rob长度为treasure的长度，rob[i]表示打劫到下标为i的家户时可以获得的最大收益。

【初始化】先填充好第一个和第二个位置，第二个位置取前两个家户财产的最大值；

【递归】由于不能打劫相邻的家户，因此研究第i个家户时，有两种方案，即打劫这一家或者不打劫这一家，选取其中较大值即可。
rob[i] = max(treasure[i] + rob[i-2], rob[i-1])

【返回值】返回打劫到最后一家的最大收益rob[-1]即可。

class Solution:
    def deleteAndEarn(self, nums) -> int:
        if not nums:
            return 0

        count = collections.Counter(nums)
        if len(count) == 1:
            return sum(nums)

        # 创造每家每户的财产列表
        treasure = [0 for _ in range(max(count.keys()))]
        for k, v in count.items():
            treasure[k-1] = k * v

        # 动态规划解决打家劫舍问题
        rob = [0 for _ in range(len(treasure))]
        rob[0], rob[1] = treasure[0], max(treasure[0], treasure[1])
        for i in range(2, len(treasure)):
            rob[i] = max(rob[i-1], treasure[i] + rob[i-2])
        return rob[-1]

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析