做网站的工作怎么样,肉山谷英雄传说新手任务登录英文网站怎么做,自适应网站推广,帝国cms做淘宝客网站力扣原题链接#xff0c;点击跳转。
给你一个整数数组nums。每次操作#xff0c;可以删除任意一个值n#xff0c;接着获得点数n#xff0c;并同时删除所有的n-1和n1。你最多能获取多少点数#xff1f;
这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序…力扣原题链接点击跳转。
给你一个整数数组nums。每次操作可以删除任意一个值n接着获得点数n并同时删除所有的n-1和n1。你最多能获取多少点数
这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序的思路定义一个数组arr用arr[i]表示所有的点数i的和。比如nums数组1、2、2、3、3、3那么arr数组0、1、4、9因为1出现1次和为12出现2次和为2×243出现3次和为3×39。
盯着这个arr数组问题就转化为在arr数组中选取一个子数组不能同时选取相邻的元素请找出一个子数组让这个子数组所有元素的和最大。如果你看到这里觉得这道题跟某一道经典问题很像有这种感觉就对了。具体请看我的另一篇博客「动态规划」打家劫舍点击跳转。有了打家劫舍的铺垫这个问题就非常简单了思路可以说是一模一样。
用动态规划的思路来解决这个问题。首先确定状态表示用f[i]表示选到下标为i的元素时必须选择下标为i的元素子数组的最大和用g[i]表示选到下标为i的元素时不能选择下标为i的元素子数组的最大和。接着推导状态转移方程显然f[i]g[i-1]arr[i]g[i]max(f[i-1],g[i-1])。初始化f[0]arr[0]0g[0]0。为什么arr[0]0呢因为点数0不管选多少和都是0。填表时应从左往右同时填表。arr有n个元素最后返回max(f[n-1],g[n-1])。
class Solution
{
public:int deleteAndEarn(vectorint nums){const int N 10001;// 用arr[i]表示所有点数i的和vectorint arr(N);for (auto num : nums)arr[num] num;// 创建dp表vectorint f(N);auto g f;// 填表for (int i 1; i N; i){f[i] g[i - 1] arr[i];g[i] max(f[i - 1], g[i - 1]);}return max(f[N - 1], g[N - 1]);}
};
