leetcode刷题(2022.05.15)
740. Delete and Earn
难度：中等。
题目大意：
给一个数组，在数组中获得满足要求的最大分数。
要求：对于取得x的分数，x-1和x+1的分数不能获得。
其实跟之前那个差不多，做了一次转换而已
解题思路
统计每个数字出现的数量，然后找当前位置的最大分数。
对于第i个位置存在:
d
p
[
i
]
=
m
a
x
(
n
u
m
[
i
]
?
i
+
d
p
[
i
?
2
]
,
d
p
[
i
?
1
]
)
dp[i]=max(num[i]*i+dp[i-2],dp[i-1])
dp[i]=max(num[i]?i+dp[i?2],dp[i?1])
其中num[i]里面记录的是i出现的次数。因为数量级不大，直接开了num[10002]用来存，然后遍历一个最大的ans。
代码
class Solution {
public:
int dp[10002]={0};
int num[10002]={0};
int deleteAndEarn(vector<int>& nums) {
int n=nums.size();
if(n==1)return nums[0];
for(int i=0;i<n;i++)
{
++num[nums[i]];
}
dp[1]=dp[0]>num[1]?dp[0]:num[1];
int ans=-1;
for(int i=2;i<10002;i++)
{
dp[i]=num[i]*i+dp[i-2]>dp[i-1]?num[i]*i+dp[i-2]:dp[i-1];
ans=max(ans,dp[i]);
}
return ans;
}
};
过题情况
时间复杂度O(1^4+N)
空间复杂度O(2*10^4)
优化
优化方法还有很多，比如在dp和num数组中有很多是浪费的可以不去记录等等。
