[740] 删除并获得点数

给你一个整数数组 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 个点数。

这道题是一道求最值的题目，因此首先考虑使用动态规划来解。

由于选择某个数，获取点数后，将不能再选取其相邻的数，因此我们能够大概推导出来，Sn 应该是跟相邻 Sn-1 和间隔 Sn-2 有关。

这里我们可以先构造出来一个相邻数的个数表 counts。

当 counts 选取一个元素 i 时，其获得的分数为 i * counts[i]，并且此时，不能再选取其相邻的 counts[i-1] 中的分数了。此时分数为：只有count[i-2]个元素获取分数的最大值 + i * counts[i]；

若不选取元素i时，此时获取的分数与只有count[i-1]个元素获取分数最大值相同。

于是我们可以得出状态转移方程：

Sn = Math.max(Sn-2 + i * counts[i], Sn-1)

这样很容易让我们联想到之前做过经典的打家劫舍问题。实际上，这就是一个换皮的打家劫舍，实现起来不难。不过，理解并抽象出来状态转移方程，将元素的个数：counts数组作为打家劫舍问题的入参，这个是比较难想到的，需要大量的做题经验堆积出来。

function deleteAndEarn(nums: number[]): number {
  if (nums.length === 1) return nums[0];
  // 获取 nums 中最大的点数
  const maxNum = nums.reduce((prev, curr) => Math.max(prev, curr));

  // 统计各点数 i 分别有多少个
  const counts: number[] = Array(maxNum + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    counts[nums[i]] += 1;
  }

  return helper(counts);

  function helper(counts: number[]) {
    let prev = counts[0];
    let curr = Math.max(counts[0], counts[1]);
    for (let i = 2; i < counts.length; i++) {
      const temp = Math.max(prev + i> counts[i], curr);
      prev = curr;
      curr = temp;
    }
    return curr;
  }
}