Delete and Earn

Question

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.

Solution

這題是 Pocket Gems 的 OA 題，當時沒寫出來，隔天想了一下覺得有可能是正確的解法，結果在這次的 contest 發現那個解法是錯的。 其實這題的核心思路還是在經典的 DP house robber 那題，只是變了形。有兩個地方需要特別注意：

1. 需要把 array 轉成 bucket，這樣一來就可以把這題轉化成 house robber
2. 轉移方程 dp[i] = Math.max(dp[i - 1], dp[i - 2] + sum[i]); 這邊比較需要思考的是這個 sum[i]。其實一樣，我們可以先把規模弄小，思考一下原本的 initilization，當 dp[1] = sum[1]，為什麼，因為 sum[0] 絕對等於 0，所以要拿一定是拿 sum[1]，因此我們會發現，其實跟該 index 的 sum[] 有關

    public int deleteAndEarn(int[] nums) {
        int[] sum = new int[10000 + 1];
        for (int num : nums) {
            sum[num] += num;
        }

        int[] dp = new int[10000 + 1];
        dp[0] = 0;
        dp[1] = sum[1];
        for (int i = 2; i <= 10000; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + sum[i]);
        }
        return dp[10000];
    }