题目
对于该题的题目分析,已经代码分析都一并写入到了代码注释中文章来源地址https://www.toymoban.com/news/detail-686365.html
代码
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 数组的下标也要有10000
int 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]);
}
}
文章来源:https://www.toymoban.com/news/detail-686365.html
到了这里,关于Java 动态规划 Leetcode 740. 删除并获得点数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!