题目

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

题解

建立 help 数组，相当于一个（正向）索引表。

先排序，因为删除的顺序不影响最优结果（实际上是影响结果的，只不过最优解一定是从小到大删除的，因为如果先删除中间的元素的话，它的两边可能被误伤，而如果从边缘开始删除的话，只能误伤到一侧。）

class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            int count = map.getOrDefault(n, 0);
            map.put(n, count + 1);
        }

        int[][] help = new int[map.keySet().size()][2];
        int p = 0;
        for (int k : map.keySet()) {
            help[p][0] = k;
            help[p++][1] = map.get(k);
        }
        // 删除顺序不影响结果（至少从小到大删除结果不会更差），所以先排序
        Arrays.sort(help, Comparator.comparingInt(o -> o[0]));

        // Approach 2: Recursion with Memoization
// return process(help, 0, dp);

        // Approach 3: Dynamic Programming
        int[] dp = new int[help.length + 2];
        Arrays.fill(dp, -1);
        dp[help.length] = 0;
        dp[help.length + 1] = 0;
        for (int i = help.length - 1; i >= 0; i--) {
            int step = (i + 1 < help.length && help[i][0] + 1 == help[i + 1][0]) ? 2 : 1;
            dp[i] = Math.max(dp[i + 1], dp[i + step] + help[i][0] * help[i][1]);
        }
        return dp[0];

    }

    // 在当前i位置，删或不删，能够获得的最大收益
// public int process(int[][] help, int i, int[] dp) {
// if (i >= help.length) return 0;
// if (dp[i] >= 0) return dp[i];
//
// int step = (i + 1 < help.length && help[i][0] + 1 == help[i + 1][0]) ? 2 : 1;
// int p1 = process(help, i + 1, dp); // 不删i位置
// int p2 = process(help, i + step, dp) + help[i][0] * help[i][1]; // 删i位置
//
// dp[i] = Math.max(p1, p2);
// return dp[i];
// }
}