力扣740. 删除并获得点数

发布时间:2024年01月22日

动态规划

  • 思路:
    • 选择元素 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;
    }
};

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

文章来源:https://blog.csdn.net/N_BenBird/article/details/135759867
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。