leetcode 740. Delete and Earn | 740. 删除并获得点数（暴力递归-＞傻缓存-＞DP）

本文主要是介绍leetcode 740. Delete and Earn | 740. 删除并获得点数（暴力递归-＞傻缓存-＞DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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 Programmingint[] 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];
//    }
}