删掉再赚到

发表于 | 更新于 | 分类于

删掉再赚到

Question

这是LeetCode第740题。

给你一个整数数组nums，你可以在数组上做如下操作：你可以选择任意一个数字nums[i]把它删掉并赚到nums[i]个点。此后，你必须删除数组中所有值为nums[i]-1和nums[i]+1的数字。你最开始有0个点。请问你如此执行操作最多能从数组上赚到多少个点？假设数组中的数字在[1, 10000]的范围之内。

例如假设输入数组nums为[2, 2, 3, 3, 3, 4]，你最多可以赚到9个点。你的最佳方案是删掉一个3赚到3个点。此时需要删掉所有的2和4。接下来你可以再删掉一个3赚到3个点。由于所有的2和4都已经删掉了，你不需要再删除更多的数字。然后你再删掉最后一个3再赚到3个点。因此你一共赚到9个点。

Analysis

  • 动态规划

    创建一个长度为10001的数组vals。该数组中下标为m的数值为原数组nums中所有值为m的数字的和（数值m可能在数组nums中出现0次、一次或者多次）。

    根据题目的规则，如果我们赚到数组nums中值为m的点数，那么我们将不能赚到所有值为m-1和m+1的点数。那么在数组vals中如果我们赚到了下标为m的数字对应的点数，那么就不能赚到下标为m-1和m+1的数字对应的点数。

    如果我们用函数f(i)表示在数组vals中前i个数字中最多能够赚到的点数，f(i)=max(f(i-1), vals[i]+f(i-2))。这是一个典型的可以用动态规划求解的问题。

    由于我们只需要保存f(i-1)和f(i-2)的值就能求得f(i)的值，因此我们在求解过程中只需要使用两个变量存储之前子问题的解即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np
def delete_and_earn(list_a):
    count_array = np.zeros(10001, dtype=np.int)
    for elem in list_a:
        count_array[elem] += elem
    val1 = 0
    val2 = count_array[1]
    max_val = val2
    for index in range(2, 10001):
        max_val = max(val2, val1 + count_array[index])
        val1 = val2
        val2 = max_val
    return max_val

list_a = [2,2,3,3,3,4,4,4,5,5]
print(delete_and_earn(list_a))
19

1
2