LeetCode 740 - Delete and Earn

https://leetcode.com/problems/delete-and-earn/description/

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.

Each element nums[i] is an integer in the range [1, 10000].

    int deleteAndEarn(vector<int>& nums) {

        if (nums.empty()) return 0;

        const auto range = minmax_element(nums.begin(), nums.end());

        const int l = *(range.first);

        const int r = *(range.second);        

        vector<int> points(r - l + 1, 0);

        for (const int num : nums)

            points[num - l] += num;

        return rob(points);

    }

private:

    // From LeetCode 198. House Robber

    int rob(const vector<int>& nums) {

        int dp2 = 0;

        int dp1 = 0;

        for (int i = 0; i < nums.size() ; ++i) {

            int dp = max(dp2 + nums[i], dp1);

            dp2 = dp1;

            dp1 = dp;

        }

        return dp1;

    }

http://buttercola.blogspot.com/2018/10/leetcode-740-delete-and-earn.html

There are several tricks in the problem.
 -- Since each element nums[i] is within the range of [1, 10000], we can use the bucket sort to sort the nums.
 -- For deleting each nums[i], we can delete all same numbers together. So when we do the bucket sort, we can sum up all the repeated numbers in the same bucket. 
 -- Then the problem is a classic backpack problem. 

Define take[10001] and skip[10001], where take[i] means for number i, we delete the number i, the max number of points. skip[i] means we don't delete it.

Then the transit function should be:
take[i] = skip[i - 1] +  values[i]
skip[i] = Math.max(take[i - 1], skip[i - 1]);

http://www.cnblogs.com/grandyang/p/8176933.html

好了，来做题吧。这道题给了我们一个数组，每次让我们删除一个数字，删除的数字本身变为了积分累积，并且要同时移除之前数的加1和减1的数，但此时移除的数字不累计积分，让我们求最多能获得多少积分。博主最开始尝试的方法是积分大小来排列，先删除大的数字，但是不对。于是乎，博主发现相同的数字可以同时删除，于是就是建立了每个数字和其出现次数之间的映射，然后放到优先队列里，重写排序方式comparator为数字乘以其出现次数，先移除能产生最大积分的数字，可是还是不对。其实这道题跟之前那道House Robber的本质是一样的，那道题小偷不能偷相邻的房子，这道题相邻的数字不能累加积分，是不是一个道理？那么对于每一个数字，我们都有两个选择，拿或者不拿。如果我们拿了当前的数字，我们就不能拿之前的数字（如果我们从小往大遍历就不需要考虑后面的数字），那么当前的积分就是不拿前面的数字的积分加上当前数字之和。如果我们不拿当前的数字，那么对于前面的数字我们既可以拿也可以不拿，于是当前的积分就是拿前面的数字的积分和不拿前面数字的积分中的较大值。这里我们用take和skip分别表示拿与不拿上一个数字，takei和skipi分别表示拿与不拿当前数字，每次更新完当前的takei和skipi时，也要更新take和skip，为下一个数字做准备，最后只要返回take和skip中的较大值即可

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-740-delete-and-earn/
Because all numbers are positive, if we "take" a number (use it to score points), we might as well take all copies of it, since we've already erased all its neighbors. We could keep a count of each number so we know how many points taking a number is worth total.

Now let's investigate what happens when we add a new number X (plus copies) that is larger than all previous numbers. Naively, our answer would be the previous answer, plus the value of X - which can be solved with dynamic programming. However, this fails if our previous answer had a number taken that was adjacent to X.

Luckily, we can remedy this. Let's say we knew using, the value of our previous answer, and avoid, the value of our previous answer that doesn't use the previously largest value prev. Then we could compute new values of using and avoid appropriately.

Algorithm

For each unique value k of nums in increasing order, let's maintain the correct values of avoid and using, which represent the answer if we don't take or take k respectively.

If the new value k is adjacent to the previously largest value prev, then the answer if we must take k is (the point value of k) + avoid, while the answer if we must not take k is max(avoid, using). Similarly, if kis not adjacent to prev, the answer if we must take k is (the point value of k) + max(avoid, using), and the answer if we must not take k is max(avoid, using).

At the end, the best answer may or may not use the largest value in nums, so we return max(avoid, using).

Our demonstrated solutions showcase two different kinds of sorts: a library one, and a radix sort. For each language, the other kind of solution can be done without much difficulty, by using an array (Python) or HashMap (Java) respectively.

• Time Complexity (Python): $O(N \log N)$, where $N$ is the length of nums. We make a single pass through the sorted keys of $N$, and the complexity is dominated by the sorting step.
• Space Complexity (Python): $O(N)$, the size of our count.
• Time Complexity (Java): We performed a radix sort instead, so our complexity is $O(N+W)$ where $W$ is the range of allowable values for nums[i].
• Space Complexity (Java): $O(W)$, the size of our count.

  public int deleteAndEarn(int[] nums) {

    int[] count = new int[10001];

    for (int x : nums)

      count[x]++;

    int avoid = 0, using = 0, prev = -1;

    for (int k = 0; k <= 10000; ++k)

      if (count[k] > 0) {

        int m = Math.max(avoid, using);

        if (k - 1 != prev) {

          using = k * count[k] + m;

          avoid = m;

        } else {

          using = k * count[k] + avoid;

          avoid = m;

        }

        prev = k;

      }

    return Math.max(avoid, using);

  }

https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation

1. If we sort all the numbers into buckets indexed by these numbers, this is essentially asking you to repetitively take an bucket while giving up the 2 buckets next to it. (the range of these numbers is [1, 10000])
2. The optimal final result can be derived by keep updating 2 variables skip_i, take_i, which stands for:
   skip_i : the best result for sub-problem of first (i+1) buckets from 0 to i, while you skip the ith bucket.
   take_i : the best result for sub-problem of first (i+1) buckets from 0 to i, while you take the ith bucket.
3. DP formula:
   take[i] = skip[i-1] + values[i];
skip[i] = Math.max(skip[i-1], take[i-1]);
take[i] can only be derived from: if you skipped the [i-1]th bucket, and you take bucket[i].
   skip[i] through, can be derived from either take[i-1] or skip[i-1], whatever the bigger;

 * for numbers from [1 - 10000], each has a total sum sums[i]; if you earn sums[i], you cannot earn sums[i-1] and sums[i+1]
 * kind of like house robbing. you cannot rob 2 connected houses.

    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        int[] values = new int[n];
        for (int num : nums)
            values[num] += num;

        int take = 0, skip = 0;
        for (int i = 0; i < n; i++) {
            int takei = skip + values[i];
            int skipi = Math.max(skip, take);
            take = takei;
            skip = skipi;
        }
        return Math.max(take, skip);
    }

https://leetcode.com/problems/delete-and-earn/discuss/109871/Awesome-Python-4-liner-with-explanation-Reduce-to-House-Robbers-Question
The condition that we cannot pick adjacent values is similar to the House Robber question that we cannot rob adjacent houses. Simply pass points into the robfunction for a quick win

https://leetcode.com/problems/delete-and-earn/discuss/109889/Java-Easy-DP-Solution

Time: O(M+N)
Space: O(N)

M: the length of input array
N: the range of the value of each int element

public int deleteAndEarn(int[] nums) {
    int[] count = new int[10001];
    for(int n : nums){
        count[n] += n;
    }
    int[] dp = new int[10003];
    for(int i = 10000; i >= 0; i--) {
        dp[i] = Math.max(count[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[0];
}

    public int deleteAndEarn(int[] nums) {
        int[] count = new int[10001];
        for (int x: nums) count[x]++;
        int avoid = 0, using = 0, prev = -1;

        for (int k = 0; k <= 10000; ++k) if (count[k] > 0) {
            int m = Math.max(avoid, using);
            if (k - 1 != prev) {
                using = k * count[k] + m;
                avoid = m;
            } else {
                using = k * count[k] + avoid;
                avoid = m;
            }
            prev = k;
        }
        return Math.max(avoid, using);
    }
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)


下面这种解法直接使用sums数组来更新，而没有使用额外的变量。上面解法中没有讲解这个sums数组，这里的sums实际上相当于建立了数字和其总积分的映射，这里的总积分的计算方法是由数字乘以其出现次数得来的。由于题目中说了每个数字不会超过10000，所以sums的长度可以初始化为10001，然后遍历原数组，将遇到的数字都累加到该数字在数组中的位置上。然后从sums数组的第三个数字开始遍历，更新方法跟上面解法的思路很类似，当前的sums[i]值就等于前一个值sums[i-1]和前两个值sums[i-2]加上当前的sums[i]值中的较大值，其实思想就是在不拿当前数的积分，跟不拿前一个数的积分加上当前的积分之和，取二者中的较大值更新当前值sums[i]

    int deleteAndEarn(vector<int>& nums) {
        vector<int> sums(10001, 0);
        for (int num : nums) sums[num] += num;
        for (int i = 2; i < 10001; ++i) {
            sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]);
        }
        return sums[10000];
    }