LeetCode 740. 删除与获得点数--动态规划

  1. 删除与获得点数

给定一个整数数组 nums ,你可以对它进行一些操作。

每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1:

输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数,因此 3 也被删除。
之后,删除 2 来获得 2 个点数。总共获得 6 个点数。

示例 2:

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数,接着要删除两个 2 和 4 。
之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
总共获得 9 个点数。

注意:

nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。

题解:

点击这里查看同类题目:LeetCode算法题目合集

可以知道一件事,那就是如果选择了某个数字x,那最优的情况肯定是选择数组里面所有的x,这个不难理解。于是先排序,然后累计下数目,用结构体储存下,

    struct Node
    {
        int val;
        int ans;
    };

val表示数字,ans表示这个数字出现的个数,然后可以得到新的数组,于是我们进行动态规划,每个数字有两种状态,取(1)或者不取(0),于是针对数字q[i].val,状态转移方程就是

            if(q[i].val==q[i-1].val+1)//说明后面的数字和前面的数字存在影响关系
            {
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);//第i个不取,那么就选择前面最大的结果
                dp[i][1]=dp[i-1][0]+q[i].val*q[i].ans;//第i个要取,只能让第i-1个不取
            }
            else//此时前后两个数字不存在影响关系了
            {
            //下面同理
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=max(dp[i-1][0],dp[i-1][1])+q[i].val*q[i].ans;
            }

AC代码

class Solution {
public:
    struct Node
    {
        int val;
        int ans;
    };
    vector<Node>q;
    bool vis[20010];
    int dp[200010][2];
    int deleteAndEarn(vector<int>& nums) {
        if(nums.size()==0)return 0;
        sort(nums.begin(),nums.end());
        Node t;
        t.val=nums[0],t.ans=1;
        q.push_back(t);
        for(int i=1;i<nums.size();i++)
        {
            int n=q.size();
            t=q[n-1];
            if(nums[i]==t.val)
            q[n-1].ans++;
            else
            {
                t.val=nums[i];
                t.ans=1;
                q.push_back(t);
            }
        }
        int res=0;
        memset(dp,0,sizeof(dp));
        dp[0][0]=0;
        dp[0][1]=q[0].val*q[0].ans;
        for(int i=1;i<q.size();i++)
        {
            if(q[i].val==q[i-1].val+1)
            {
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][0]+q[i].val*q[i].ans;
            }
            else
            {
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=max(dp[i-1][0],dp[i-1][1])+q[i].val*q[i].ans;
            }
        }
        return max(dp[q.size()-1][0],dp[q.size()-1][1]);
    }
};

LeetCode 740. 删除与获得点数--动态规划

上一篇:【DB笔试面试740】在Oracle中,集群中的Master Node体现在哪两个方面?


下一篇:740. 删除与获得点数