Java 动态规划 Leetcode 740. 删除并获得点数

题目

对于该题的题目分析，已经代码分析都一并写入到了代码注释中

代码

class Solution {public int deleteAndEarn(int[] nums) {//核心思路：//由于我们获得 nums[i] 的点数之后，就必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素//假设我们现在要解决的数组为 1，2，3，4，5 当我们获得2的点数就不能获得 1，3 的点数，我们的选择就是 2，4 或者 1，3，5（即相邻的点数不能获取）//这样明显问题就简单了许多，所以我们要进行处理，将源数组转换为0，1，2，3...顺序排序的形式//我们可以创建一个辅助数组 arr ，让 arr 的下标表示源数组 nums[i] 的值， arr 的值表示源数组 nums[i] 值的总和//例如：对于nums=[2,2,3,3,3,4]//         arr=[0,0,4,9,4]//         下标：0,1,2,3,4//对于arr数组，我们就可以转换问题为相邻的点数不能获取求最大点数//由于 arr 数组的下标表示 nums 数组的值，而 nums 数组的值的最大值为10000（由题可知），所以 arr 数组的下标也要有10000int n=10001;int[] arr=new int[n];//初始化arr数组for(int x:nums){arr[x]+=x;}//创建dp表//对于arr数组中的点数我们可以选择要也可以选择不要//假设 f[i] 表示下标为i的点数我们必定要时所得的点数最大值， g[i] 表示下标为i的点数我们必定不要时所得的点数最大值// f[i] 由于下标为i的点数我们必定要，所以下标i-1的点数我们必定不要，那么到下标 i 我们能够获得的最大点数为f[i]=g[i-1]+arr[i]// g[i] 由于下标为i的点数我们必定不要，所以下标为 i-1 的点数我们可以选择要也可以选择不要，由于我们要求最大点数，所以我们应该选择点数较大的情况//g[i]=Math.max(f[i-1],g[i-1])//由于点数最大能达到10000，所以我们最大要判断10000这个点数是要还是不要，所以f数组和g数组都要开辟10001的大小int[]f=new int[n];int[]g=new int[n];//初始化//根据上面对f数组和g数组的分析，我们知道 i 的取值应该从1开始，所以我们需要知道f[0]和g[0]的值f[0]=arr[0];//g[0]=0;//填充dp数组for(int i=1;i<n;i++){f[i]=g[i-1]+arr[i];g[i]=Math.max(f[i-1],g[i-1]);}//返回值//当我们填充完f和g数组后，我们就知道了最后一个数选和不选的最大值，由于我们要的是最大点数，所以返回的应该是两个最大值中较大的一个return Math.max(f[n-1],g[n-1]);}
}