自己尝试第一次解无果只能看答案,读了一遍官方解答理解思路后,学习答案中将问题转化为有序数组然后dp的思想,然后尝试自己编码解决。 因为数据本身是无序的,取一个nums[i]势必得考虑其相邻值nums[i]-1和nums[i]+1的取舍,直接dp无疑涉及多次遍历查找之类的操作,所以我们做一个排序,将相邻数据摆在一块,数据取舍会更加方便一些,也更容易写dp状态迁移方程。
这里我采用的是C++STL中的map,主要是利用其自动排序的特征和可以迭代的特性,首先将nums转化成元素结构为(key=nums[i],value=重复次数)的有序索引表tnums,状态迁移方程如下
dp[key]=dp[上一个索引key]+tnums[key]*key 其中key!=上一个索引key+1 dp[key]=max{dp[key-1],dp[key-1的上一个索引key]+tnums[key]*key } 此时key==上一个索引key+1
代码如下:
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int length=nums.size();
map<int,int> tnums;
for(int i=0;i<length;i++)
{
if(!tnums.count(nums[i]))
tnums.insert(map<int, int>::value_type (nums[i],1));
else
tnums[nums[i]]+=1;
}
int first=0;
int second=0;
length=tnums.size();
map<int,int>::iterator it;
it=tnums.begin();
first=it->first*it->second;
if(length==1)
return first;
map<int,int>::iterator last_it=it;
it++;
for(;it!=tnums.end();it++)
{
if((last_it->first)+1!=it->first)
{
second=first;
first=first+(it->first)*(it->second);
}
else
{
int t=first;
first=(second+(it->first)*(it->second))>(first)?(second+(it->first)*(it->second)):first;
second=t;
}
last_it=it;
}
return first;
}
};
|