题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一串无序、可重复的整数，可以任取其中的一个数字加入，但取数的同时，该数值相邻（+1或-1）的值都会删除，求如何取数能最大。

思路分享

  • 读题有个陷阱，取数才算值，删除的不算，这么一来就变成了不能偷盗相邻房屋的打家劫舍问题。

  • 划分子问题就可以是截止到数值 i（i-1、i-2……）可获得的最大数值

  • 状态转移方程为 f[i] = max(f[i-1], f[i-2]+val[i])，其中 val 可以代表该值的总和。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        n = len(nums)
        a = [0] * (max(nums)+1)
        for x in nums:
            a[x] += x

        f = [0] * len(a)
        f[0] = a[0]
        f[1] = a[1]
        for i in range(len(a)-2):
            f[i+2] = max(f[i+1], f[i]+a[i+2])

        return f[len(a)-1]