本文主要是介绍每日一题(力扣740):删除并获得点数--dp+思维,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
其实跟打家劫舍没啥区别 排序去重之后去考虑当前位置和前两个位置之间的关系即可,具体见代码:
class Solution {
public:int deleteAndEarn(vector<int>& nums) {int n = nums.size();if (n == 1) return nums[0];unordered_map<int, int> hash;for (int i = 0; i < n; i++) {++hash[nums[i]];}sort(nums.begin(), nums.end());int n1 = (unique(nums.begin(), nums.end()) - nums.begin());vector<int> dp(n1 + 1, 0);dp[0] = 0; dp[1] = nums[0] * hash[nums[0]];for (int i = 1; i < n1; i++) {if (nums[i] - nums[i - 1] == 1) {dp[i + 1] = max(dp[i - 1] + nums[i] * hash[nums[i]], dp[i]);}else {dp[i + 1] = dp[i] + nums[i] * hash[nums[i]];}}return dp[n1];}
};
这篇关于每日一题(力扣740):删除并获得点数--dp+思维的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!