本文主要是介绍力扣740. 删除并获得点数(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述:
给你一个整数数组 nums
,你可以对它进行一些操作。
每次操作中,选择任意一个 nums[i]
,删除它并获得 nums[i]
的点数。之后,你必须删除 所有 等于 nums[i] - 1
和 nums[i] + 1
的元素。
开始你拥有 0
个点数。返回你能通过这些操作获得的最大点数。
示例 1:
输入:nums = [3,4,2] 输出:6 解释: 删除 4 获得 4 个点数,因此 3 也被删除。 之后,删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2:
输入:nums = [2,2,3,3,3,4] 输出:9 解释: 删除 3 获得 3 个点数,接着要删除两个 2 和 4 。 之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。 总共获得 9 个点数。
提示:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
思路:
根据题目意思我们可以很容易得到,如果我们要选择删除x,那么我们会将所有的x+1和x-1的元素全部删掉并获得x点数,换句话说,我们选择不能同时同时获得x和x+1点数或者是x和x-1点数。因为,如果获得了x点数,x+1的元素与x-1的元素就已经全部不存在了,而如果有多个x,我们就可以获得这些x总和的点数。
我们可以用sum[x]表示元素x的总和点数。
那么这个题和打家劫舍就一样了,求不能选相邻元素的最大点数。
转化成为背包的思想--选或者不选
选x,就要加上所有x总和的点数,这个状态是由x-2转移过来的
不选x,那么上一个状态就是x-1
用f[x]表示在0--x里面选不相邻的值,获得的最大点数。
f[x]=max(f[x-1],f[x-2]+sum[x])
代码:
class Solution {
public:int deleteAndEarn(vector<int>& nums) {int len=nums.size();int max_v=0;//记录nums数组里最大的数,也就是数组sum的下标范围for(int i=0;i<len;i++){if(nums[i]>max_v){max_v=nums[i];}}vector<int> sum(max_v+10,0);for(int i=0;i<len;i++){sum[nums[i]]+=nums[i];//sum[nums[i]]表示值为nums[i]的总和}vector<int> f(max_v+1,0);f[0]=sum[0];f[1]=max(sum[1],sum[0]);for(int i=2;i<=max_v;i++){f[i]=max(f[i-1],f[i-2]+sum[i]);}return f[max_v];}
};
这篇关于力扣740. 删除并获得点数(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!