我在解决这个动态规划问题的方法中缺少什么？（Leetcode 740. 删除并获得）

Question

我正在尝试了解如何解决 Leetcode Problem #740: Delete and Earn

我最近在面试前评估中遇到了这个问题，但无法在规定的时间内完成。我今天一直在研究它，试图全神贯注，但此刻我有点在原地打转。我检查了许多资源、视频、教程等，但我在 vanilla JS 中工作，很多指南都是用 C++、Python 或我目前不知道的 Typescript 编写的。（我计划至少学习 Python 和 Typescript，但我目前正在使用我当前的知识集）。这导致了混乱和沮丧，因为示例 python/c++ 代码等的准确翻译一直在困扰着我。

问题如下：

给你一个整数数组nums。您想通过多次执行以下操作来最大化您获得的点数：

选择任何 nums[i] 并将其删除以获得 nums[i] 积分。之后，您必须删除等于 nums[i] - 1 的每个元素和等于 nums[i] + 1.

的每个元素

Return 最大点数 您可以通过多次应用上述操作获得

示例 1

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

示例 2

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

我目前有：

const deleteAndEarn = (nums) => {
  if(!nums || nums.length === 0) return 0;
  if(nums.length === 1) return nums[0];
  if(nums.length === 2) return nums[1];
  
  const freq = makeDict(nums);
  let prevNum
  let [keep, avoid] = [0, 0];
  for(const num of [...Object.keys(freq)].sort()){
    let max = Math.max(keep, avoid)
    if(parseInt(num) - 1 !== prevNum){
      [keep, avoid] = [
        (freq[num] * parseInt(num)) + max,
        max
      ]
    }else{
      [keep, avoid] = [
        parseInt(num) * freq[num] + avoid,
        max
      ]
    }
    prevNum = parseInt(num)
  }
  
  return Math.max(keep, avoid)
};

const makeDict = (nums) => {
  const dict = {}
  for(const num of nums){
    dict[num] = !!dict[num] ? dict[num]++ : 1
  }
    return dict
}

提供Python解决方案

这是我试图为我的代码建模的内容，但我实际上并不知道 Python 语法，所以我确定我遗漏了一些东西。

class Solution(object):
    def deleteAndEarn(self, nums):
        count = collections.Counter(nums)
        prev = None
        avoid = using = 0
        for k in sorted(count):
            if k - 1 != prev:
                avoid, using = max(avoid, using), k * count[k] + max(avoid, using)
            else:
                avoid, using = max(avoid, using), k * count[k] + avoid
            prev = k
        return max(avoid, using)

我真的完全不明白为什么这段代码不起作用，我什至一步一步地走到了运行个示例案例。请帮助我了解如何执行此操作，以便我找到工作！

非常感谢

Answer 1

您现有代码中的一个错误是

[...Object.keys(freq)].sort()

不会按顺序对数字进行排序 - 请参阅 here。

另一个错误是你的算法没有任何回溯 - 你不想在给定的情况下贪婪地选择 3 [3, 4, 4, 4]。

我认为解决这个问题的最好方法是理解它只是输入中需要考虑的连续数字字符串。例如，给定

[1, 2, 3, 6, 7, 8]

把它分成所有连续的整数串：

[1, 2, 3]
[6, 7, 8]

然后决定每个序列的最佳选择。

您不能只选择序列中的所有奇数或所有偶数，因为那样会无法选择，例如 [1, 1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4] 的 1 和 4。我能看到的最好的方法是使用递归函数：检查序列时，getBestSequenceSum，从 N 开始，return 的最大值：

N 加 getBestSequenceSum(seq.slice(2)) 的总和（跳过序列中的下一项），或
getBestSequenceSum(seq.slice(1)) 的总和（使用序列中的下一项）

充分涵盖所有可能性。

可能还有更高效的算法，但这相对简单直观。

const getBestSequenceSum = (seq) => {
  if (seq.length === 0) return 0;
  // Include the lowest value in the sequence, or not?
  const sumOfLowestVal = seq[0].num * seq[0].count;
  
  return Math.max(
    sumOfLowestVal + getBestSequenceSum(seq.slice(2)),
    getBestSequenceSum(seq.slice(1))
  );
};
const deleteAndEarn = (nums) => {
  nums.sort((a, b) => a - b);
  let lastNum;
  const sequences = [];
  for (const num of nums) {
    if (num !== lastNum && num !== lastNum + 1) {
      // New sequence
      sequences.push([]);
    }
    const thisSequence = sequences[sequences.length - 1];
    if (num !== lastNum) {
      thisSequence.push({ num, count: 0 });
    }
    thisSequence[thisSequence.length - 1].count++;
    lastNum = num;
  }
  return sequences.reduce((a, seq) => a + getBestSequenceSum(seq), 0);
};

console.log(deleteAndEarn([10,8,4,2,1,3,4,8,2,9,10,4,8,5,9,1,5,1,6,8,1,1,6,7,8,9,1,7,6,8,4,5,4,1,5,9,8,6,10,6,4,3,8,4,10,8,8,10,6,4,4,4,9,6,9,10,7,1,5,3,4,4,8,1,1,2,1,4,1,1,4,9,4,7,1,5,1,10,3,5,10,3,10,2,1,10,4,1,1,4,1,2,10,9,7,10,1,2,7,5]));

通过将 { num, count: 0 } 对象更改为单个数字，可以稍微减少计算次数，但这在阅读代码时会更难理解。

您还可以通过缓存已经优化的序列来减少计算次数，以免多次重新计算它们，但这会使代码显着变长。

Answer 2

我想通了！问题是双重的。

第一个错误

首先，感谢 David Eisenstat 发现了我的 makeDict() 函数中的错误。

错误的代码行如下：

dict[num] = !!dict[num] ? dict[num]++ : 1

而正确的语法如下：

dict[num] = !!dict[num] ? ++dict[num] : 1

或者

dict[num] = !!dict[num] ? dict[num] + 1 : 1

问题来自后缀与前缀增量运算符在 Javascript 中的工作方式。

From the MDN docs:

如果使用后缀，运算符在操作数之后（例如，x++），递增运算符递增，returns递增前的值。

如果使用前缀，运算符在操作数之前（例如，++x），增量运算符递增，returns递增后的值。

错误二

第二个问题来自我最初的保护条款。

if(nums.length === 2) return nums[1];

我认为这是我一开始对提供的数组进行排序时的遗留问题，但即便如此，自动选择最后一个元素也没有任何意义。我删除了这一行，结合之前makeDict()函数的调整，代码通过了所有提供的测试。

下面提供了我的工作解决方案。欢迎就如何提高代码的可读性或效率提出任何建议。

感谢帮助！

const deleteAndEarn = (nums) => {
  if(!nums || nums.length === 0) return 0;
  if(nums.length === 1) return nums[0];
  
  const freq = makeDict(nums);
  let prevNum
  let [keep, avoid] = [0, 0];
  
  for(const num of Object.keys(freq)){
    let max = Math.max(keep, avoid)
    if(parseInt(num) - 1 !== prevNum){
      [keep, avoid] = [
        (freq[num] * parseInt(num)) + max,
        max
      ]
    }else{
      [keep, avoid] = [
        parseInt(num) * freq[num] + avoid,
        max
      ]
    }
    prevNum = parseInt(num)
  }
  
  return Math.max(keep, avoid)
};

const makeDict = (nums) => {
  const dict = {}
  for(const num of nums){
    dict[num] = !!dict[num] ? ++dict[num] : 1
  }
    return dict
}

我在解决这个动态规划问题的方法中缺少什么？（Leetcode 740. 删除并获得）

What am I missing in my approach to this Dynamic Programming problem? (Leetcode 740. Delete and Earn)

javascript

algorithm

dynamic-programming

我在解决这个动态规划问题的方法中缺少什么？ （Leetcode 740. 删除并获得）

What am I missing in my approach to this Dynamic Programming problem? (Leetcode 740. Delete and Earn)

javascript

algorithm

dynamic-programming

我在解决这个动态规划问题的方法中缺少什么？（Leetcode 740. 删除并获得）