【5.5】LeetCode每日一题· 删除并获得点数

2021年05月05日 16时45分

标签： LeetCode 动态规划

## 题目描述
给你一个整数数组nums，你可以对它进行一些操作。

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

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

#### 示例1
```
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
```

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

#### 提示
```
1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4
```

#### 来源

> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/delete-and-earn%0A)

## 解题思路
首先最重要的一点是理解题意。当我们选择一个`nums[i]`，获得点数后，还要删除每个等于`nums[i] - 1`或`nums[i] + 1`的元素，这里**删除**的意思其实是，我们之后就不能选择值为`nums[i] - 1`和`nums[i] + 1`的元素了。

显然，如果某一个元素被选中后，所有和该元素值相同的其他元素也应该被选中，否则不可能获得最大点数，而选中这些元素所获的的点数和就是`nums[i]的值乘上元素个数`。同时考虑到`nums[i] - 1 < nums[i] < nums[i] + 1`，因此可以将`nums`从小到大排序，那么`nums[i] - 1`仅可能是`nums[i]`的前一个元素，`nums[i] + 1`仅可能是`nums[i]`的后一个元素。

因此，可以将`nums`数组中的所有元素从小到大排序，然后将相同元素合并成一个元素：记录每个元素出现的个数到二元组数组`a`，其中`a[i].first`表示元素的值，`a[i].second`表示该元素出现的次数。

然后，考虑到问题要求【最大点数】这一很有【最优子结构】暗示的信息，考虑使用动态规划求解，可以定义状态为：
```
dp[i][0] := a[0..i]中，且不选择a[i].first能够获得的最大点数
dp[i][1] := a[0..i]中，且必定选择a[i].first能够获得的最大点数
```
可以得到状态转移方程为：
```
dp[i][0] = max{dp[i-1][0], dp[i-1][1]};
dp[i][1] = max{dp[i-1][0], dp[i-1][1] if a[j].first != a[i].first-1 else 0} + a[i].first * a[i].second;
```

最后，就可以在 $$O(N\\log N)$$（排序$$O(N\log N)$$，动态规划递推$$O(N)$$）时间内解决问题。

## 代码
```cpp
class Solution {
public: 
    // dp[i][0] := a[0..i]中，且不选择a[i].first能够获得的最大点数
    // dp[i][1] := a[0..i]中，且必定选择a[i].first能够获得的最大点数
    // dp[i][0] = max{dp[i-1][0], dp[i-1][1]};
    // dp[i][1] = max{dp[i-1][0], dp[i-1][1] if a[j].first != a[i].first-1 else 0} + a[i].first * a[i].second;
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<pair<int, int>> a;
        for(int i = 0; i < nums.size(); i++){
            if(i == 0 || nums[i] != nums[i-1]){
                a.push_back({nums[i], 1});
            }else{
                a.back().second++;
            }
        }
        int dp[a.size()][2];
        dp[0][0] = 0;
        dp[0][1] = a[0].first * a[0].second;
        for(int i = 1; i < a.size(); i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = max(dp[i-1][0] + a[i].first*a[i].second, (a[i-1].first==a[i].first-1)? 0: dp[i-1][1] + a[i].first*a[i].second);
        }
        return max(dp[a.size()-1][0], dp[a.size()-1][1]);
    }
};
```

## 用时和内存
> 执行用时：4 ms，在所有 C++提交中击败了94.08%的用户
> 内存消耗：9 MB，在所有 C++提交中击败了55.47%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.5】LeetCode每日一题· 删除并获得点数

所有评论

暂无评论

新增评论