力扣740. 删除并获得点数

本文主要是介绍力扣740. 删除并获得点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划

• 思路：
  • 选择元素 x，获得其点数，删除 x + 1 和 x - 1，则其他的 x 的点数也会被获得；
  • 可以将数组转换成一个有序 map，key 为 x， value 为对应所有 x 的和；
  • 则问题转换成了不能同时获得相邻两个房间的金币并能获得最大收益问题：力扣198. 打家劫舍；
  • 动态规划状态转移方程 dp[i] 跟之前两个状态相关，可以使用滚动数组的方式，减少空间复杂度：
    • dp[i] = std::max(dp[i - 2] + nums[i], dp[i - 1])
    • dp0 -> dp[i - 2], dp0' = dp[i - 1]
    • dp1 -> dp[i - 1], dp1' = dp[i]
    • 在使用一个临时变量：
      • tmp = dp[i - 1] -> dp1
      • dp[i]       | -> dp1' <- dp1 = std::max(dp[i - 2] -> dp0 + nums[i], dp[i - 1] -> dp1)
      • dp[i - 1]  | -> dp1 -> tmp

class Solution {
public:int deleteAndEarn(vector<int>& nums) {int maxVal = 0;for (int val : nums) {maxVal = std::max(maxVal, val);}std::vector<int> sum(maxVal + 1);for (int val : nums) {sum[val] += val;}return rob(sum);}private:int rob(std::vector<int>& nums) {int size = nums.size();if (size == 0) {return 0;}if (size == 1) {return nums[0];}int dp0 = nums[0];int dp1 = std::max(dp0, nums[1]);for (int i = 2; i < size; ++i) {int tmp = dp1;dp1 = std::max(dp0 + nums[i], dp1);dp0 = tmp;}return dp1;}
};

——————————————————————

这篇关于力扣740. 删除并获得点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---