740 Delete and Earn
740. Delete and Earn
1. Question
Given an arraynums
of integers, you can perform operations on the array.
In each operation, you pick anynums[i]
and delete it to earnnums[i]
points. After, you must delete every element equal tonums[i] - 1
ornums[i] + 1
.
You start with 0 points. Return the maximum number of points you can earn by applying such operations.
Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
Note:
The length ofnums
is at most20000
.
Each elementnums[i]
is an integer in the range[1, 10000]
.
2. Implementation
(1) DP
思路:
(1) 这题由于选择了一个数后,就必须把比这个数小1或比这个数大于1的数给删除,所以我们需要用一个方法可以表示所有连续数字,由于数字的范围在1 - 10000,所以直接建立一个size为10000的数组dp
(2) 对于每个数,我们只有两种操作, earn it or skip it, 如果我们要earn的话,就要跳过比当前数少1的数,如果skip当前的数,则取之前的数,所以可以得到状态转移方程:
dp[i] = Math.max(dp[i - 1], dp[i - 2] + dp[i]);
(3) 上面的dp有两层含义,在第一步初始化dp数组时,dp[i]表示数字i的值总和 比如数组[3, 3, 3],dp[3] = 9。在第二步中我们要找到最大可以earn的值的时候,dp[i]此时的含义是在前[1-i]中,我们通过earn和delete的操作,可以得到的最大的值
class Solution {
public int deleteAndEarn(int[] nums) {
int n = 10001;
int[] dp = new int[n];
for (int num : nums) {
dp[num] += num;
}
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + dp[i]);
}
return dp[n - 1];
}
}
(2) 空间优化
class Solution {
public int deleteAndEarn(int[] nums) {
int n = 10001;
int[] dp = new int[n];
for (int num : nums) {
dp[num] += num;
}
int skip = 0, take = 0;
for (int i = 0; i < n; i++) {
int takei = skip + dp[i];
int skipi = Math.max(skip, take);
take = takei;
skip = skipi;
}
return Math.max(skip, take);
}
}
3. Time & Space Complexity
DP: 时间复杂度O(n), 空间复杂度O(1), 空间虽然是O(1),但实际上size是10001,涵盖数的所有范围
空间优化: 时间复杂度O(n), 空间复杂度O(1)
Last updated
Was this helpful?