740 Delete and Earn
Last updated
Was this helpful?
Last updated
Was this helpful?
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:
Example 2:
Note:
The length ofnums
is at most20000
.
Each elementnums[i]
is an integer in the range[1, 10000]
.
(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的操作,可以得到的最大的值
(2) 空间优化
DP: 时间复杂度O(n), 空间复杂度O(1), 空间虽然是O(1),但实际上size是10001,涵盖数的所有范围
空间优化: 时间复杂度O(n), 空间复杂度O(1)