740.删除并获得点数

链接：740.删除并获得点数
难度：Medium
标签：数组、哈希表、动态规划
简介：开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

题解 1 - typescript

• 编辑时间：2021-05-05
• 执行用时：108ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：动态规划，计算包含前后值和不包含前后值得情况。

function deleteAndEarn(nums: number[]): number {
  const map = new Map<number, number>();
  nums.forEach(num => map.set(num, (map.get(num) ?? 0) + 1));
  const arr = [...map.keys()].sort((a, b) => a - b);
  const len = arr.length;
  const dp: number[][] = new Array(len).fill(0).map(_ => new Array(2).fill(0));
  dp[0][0] = arr[0] * map.get(arr[0])!;
  for (let i = 1; i < len; i++) {
    const num = arr[i];
    const maxPrev = Math.max(...dp[i - 1]);
    dp[i][1] = maxPrev;
    dp[i][0] = (map.has(num - 1) ? dp[i - 1][1] : maxPrev) + map.get(num)! * num;
  }
  return Math.max(...dp[len - 1]);
}