740. 删除并获得点数https://leetcode.cn/problems/delete-and-earn/description/
给你一个整数数组nums,你可以对它进行一些操作。每次操作中,选择任意一个nums[i],删除它并获得nums[i]的点数。之后,你必须删除所有等于nums[i] - 1和nums[i] + 1的元素。开始你拥有0个点数。返回你能通过这些操作获得的最大点数。
- 输入:nums = [3,4,2],输出:6,解释:删除4获得4个点数,因此3也被删除。之后,删除2获得2个点数。总共获得6个点数。
- 输入: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。
我们用类似计数排序的思想。定义一个数组arr,arr[i]表示:在nums中,所有点数i的和。如,如果nums = [2,2,3,3,3,4],那么nums = [0,0,4,9,4],意思是:0出现0次,和为0;1出现0次,和为0;2出现2次,和为4;3出现3次,和为9;4出现1次,和为4。
那么,问题就转化为:在nums中选择一些元素,让这些元素的和最大。你不能选择相邻的元素。咦,咋这么眼熟?这不就是打家劫舍嘛!看来小偷又改行来玩游戏了,嘿嘿。我们用动态规划的思想来解决这个问题。
确定状态表示:根据经验和题目要求,我们用dp[i]表示:选到i位置的元素后,此时的最大和。再细分为:
- 用f[i]表示:必须选择i位置的元素后,此时的最大和。
- 用g[i]表示:不能选择i位置的元素后,此时的最大和。
推导状态转移方程:分别讨论2种情况中,最近的一步,即是否选择i - 1位置的元素。
- 考虑f[i]。如果选择i位置的元素,那么就不能选择i - 1位置的元素。选择完i位置的元素之后的最大和,就等于不能选择i - 1位置的元素之后的最大和加上i位置的元素,即f[i] = g[i - 1] + arr[i]。
- 考虑g[i]。如果不能选择i位置的元素,那么此时的最大和就等于考虑完i - 1元素之后的最大和。由于不确定是否选择i - 1位置的元素,所以不能选择i位置的元素后的最大和,就等于是否选择i - 1位置的元素这2种情况的最大和的较大值,即g[i] = max(f[i - 1], g[i - 1])。
综上所述:f[i] = g[i - 1] + arr[i],g[i] = max(f[i - 1], g[i - 1])。
初始化:根据状态转移方程,在计算f[0]和g[0]时会越界,所以要对其初始化。
- f[0]表示:必须选择0位置的元素之后,此时的最大和,显然f[0] = arr[0]。
- g[0]表示:不能选择0位置的元素之后,此时的最大和,显然g[0] = 0。
综上所述:f[0] = arr[0],g[0] = 0。
填表顺序:根据状态转移方程,f[i]依赖于g[i - 1],g[i]依赖于f[i - 1]和g[i - 1],所以应从左往右同时填f表和g表。
返回值:假设arr数组有n个元素。最终要返回考虑完n - 1位置的元素后,此时的最大和。由于并不确定是否选择n - 1位置的元素,再根据状态表示,我们应返回的是,是否选择n - 1位置的元素这2种情况中,最大和的较大值,即max(f[n - 1], g[n - 1])。
细节问题:由于f表和g表的下标范围是[0, n - 1],所以规模都是1 x n。
时间复杂度:O(N),空间复杂度:O(N)。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10001;
// 转化问题
vector<int> arr(N);
for (auto num : nums) {
arr[num] += num;
}
// 创建dp表
vector<int> f(N);
auto g = f;
// 初始化
f[0] = arr[0];
// 填表
for (int i = 1; i < N; i++) {
f[i] = g[i - 1] + arr[i];
g[i] = max(f[i - 1], g[i - 1]);
}
// 返回结果
return max(f[N - 1], g[N - 1]);
}
};