给你一个整数数组nums。每次操作,可以删除任意一个值n,接着获得点数n,并同时删除所有的n-1和n+1。你最多能获取多少点数?
这个问题的解法相当巧妙。我们可以把问题先转化一下。用类似计数排序的思路,定义一个数组arr,用arr[i]表示所有的点数i的和。比如nums数组:1、2、2、3、3、3,那么arr数组:0、1、4、9,因为1出现1次,和为1;2出现2次,和为2×2=4;3出现3次,和为3×3=9。
盯着这个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]=0,g[0]=0。为什么arr[0]=0呢?因为点数0不管选多少,和都是0。填表时应从左往右同时填表。arr有n个元素,最后返回max(f[n-1],g[n-1])。
class Solution
{
public:
int deleteAndEarn(vector<int>& nums)
{
const int N = 10001;
// 用arr[i]表示所有点数i的和
vector<int> arr(N);
for (auto num : nums)
arr[num] += num;
// 创建dp表
vector<int> 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]);
}
};
标签:arr,删除,nums,max,元素,数组,点数,动态
From: https://blog.csdn.net/xiang_bolin/article/details/139247873