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

I'm trying to understand how to solve Leetcode Problem #740: Delete and Earn

I recently was given this problem as part of a pre-interview assessment and was unable to complete it in the allotted time. I've been working on it today to try and wrap my head around it, but I'm kinda spinning in circles at the moment. I've checked numerous resources, videos, tutorials, etc, but I'm working in vanilla JS and a lot of the guides are in C , Python, or Typescript which I don't currently know. (I plan on learning Python and Typescript at minimum, but I'm working with my current set of knowledge for the time being). This is leading to confusion and frustration, as an accurate translation of sample python/c code, etc continues to elude me.

The problem is as follows:

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

Example 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.

Example 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.

What I have so far:

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
}

Provided Python Solution

This is what I've tried to model my code off of, but I don't actually know Python syntax so I'm sure I'm missing something.

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)

I really don't understand at all why this code isn't working, and I've even gone as far as to run sample cases step by step. Please help me understand how to do this so I can get a job!

Many thanks

CodePudding user response：

I figured it out! The problem is twofold.

Bug Number One

First, shoutout to David Eisenstat for catching the bug in my makeDict() function.

The incorrect line of code reads:

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

Whereas the correct syntax is as follows:

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

or alternatively

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

The issue comes from how postfix vs prefix increment operators work in Javascript.

From the MDN docs:

If used postfix, with operator after operand (for example, x ), the increment operator increments and returns the value before incrementing.

If used prefix, with operator before operand (for example, x), the increment operator increments and returns the value after incrementing.

Bug Number Two

The second issue comes from my initial guard clauses.

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

I think this was a remnant from when I was sorting the provided array at the very start, but even then automatically selecting the last element doesn't really make any sense. I deleted this line and, combined with the adjustment to the previous makeDict() function, the code passed all the provided tests.

My working solution is provided below. Open to any suggestions as to how to improve the code for both readability, or efficiency.

Appreciate the help!

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
}

CodePudding user response：

One bug in your existing code is that

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

will not sort numbers in order - see here.

Another bug is that your algorithm doesn't have any backtracking - you don't want to greedily choose 3 when given [3, 4, 4, 4].

I think the best way to approach this is to understand that it's only strings of consecutive numbers in the input that need to be considered. For example, given

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

Separate it out into all the consecutive strings of integers:

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

Then decide the optimal picks for each sequence.

You can't just pick all odd numbers or all even numbers in the sequence, because that would fail to pick, eg, 1 and 4 for [1, 1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4]. The best approach I can see is to use a recursive function: when checking a sequence, getBestSequenceSum, starting with N, return the maximum of:

Sum of N plus getBestSequenceSum(seq.slice(2)) (skipping the next item in the sequence), OR
Sum of getBestSequenceSum(seq.slice(1)) (using the next item in the sequence)

to adequately cover all possibilities.

There may be more efficient algorithms, but this is relatively simple and intuitive.

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]));

The number of calculations could be reduced somewhat by changing the { num, count: 0 } objects to a single number instead, but that would be more difficult to understand when reading the code.

You could also reduce the number of calculations by caching already-optimized sequences so as not to recalculate them multiple times, but that'd make the code significantly longer.