目录

740. 删除并获得点数

zxMrlc 收录于 leetcode

2021-05-04 约 374 字预计阅读 1 分钟

目录

题目

题目链接

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

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

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

分析

存在递推关系,梳理简化下条件,实际上就是拿nums[i]的时候后续不能拿取nums[i]+1
对nums去重排序后得到新的nums,dp[i]j考虑第i的时候取与不取的最优代价.

递推关系如下:

1
2
3
4
5
6
7


  # c代表nums[i]的计数
  if nums[i] - nums[i - 1] == 1:
      dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i] * c[nums[i]])
  else:
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
      dp[i][1] = dp[i][0] + nums[i] * c[nums[i]]

提交代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def deleteAndEarn(self, nums):
        from collections import Counter
        c = Counter(nums)
        nums = sorted(c.keys())
        n = len(nums)
        dp = [[0] * 2 for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = nums[0] * c[nums[0]]
        for i in range(1, n):
            if nums[i] - nums[i - 1] == 1:
                dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i] * c[nums[i]])
            else:
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
                dp[i][1] = dp[i][0] + nums[i] * c[nums[i]]
        return max(dp[-1][0], dp[-1][1])