删除并获得点数

[louzhedong]

习题

给你一个整数数组 nums ，你可以对它进行一些操作。

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

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

示例 1：

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

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

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

思路

对于数组nums中的每一个元素，我们都可以选择获取它的值或者删除它

所以对于每一个数字，是否选择它可以基于两种前置结果：

1. 如果不选择当前位置的数字，那得到的就是前一个位置数字的最优解
2. 如果选择当前位置的数字，那得到的就是前前位置数字的最优解加上当前位置数字的最优解乘以数字个数

所以本题可以采用动态规划的方式来进行解答

使用一个map来保存每个数字出现的个数

接下来写出递归公式

dp[0] = 0

dp[1] 是数字1 出现的次数

dp[i] = max(dp[i - 1], dp[i - 2] + i * map[i])

解答

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function(nums) {
    var map = {},
        numCount = 0,
        dp = [0];
    nums.forEach(function(item) {
        if (map[item]) {
            map[item] = map[item] + 1;
        } else {
            map[item] = 1;
            if (item > numCount) {
                numCount = item;
            }
        }
    })
    
    if (map[1]) {
        dp[1] = map[1];
    } else {
        dp[1] = 0;
    }

    for (var i = 2; i <= numCount; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * (map[i] || 0));
    }
    return dp.pop();
};

go

func deleteAndEarn(nums []int) int {
    numMap := make(map[int]int, 0)
    numCount := 0
    
    for _, value := range nums {
        _, ok := numMap[value]
        if !ok {
            numMap[value] = 1
            if (value > numCount) {
                numCount = value
            }
        } else {
            numMap[value] = numMap[value] + 1
        }
    }
    dp := make([]int, numCount + 1)
    dp[0] = 0
    _, ok := numMap[1]
    if !ok {
        dp[1] = 0
    } else {
        dp[1] = numMap[1]
    }

    for i :=2; i <= numCount; i++ {
        _, ok := numMap[i]
        if !ok {
            dp[i] = getMax(dp[i - 1], dp[i - 2])
        } else {
            dp[i] = getMax(dp[i - 1], dp[i - 2] + i * numMap[i])
        }
    }
    return dp[len(dp) - 1]
}

func getMax(a int, b int) int {
    if a > b {
        return a
    }
    return b
}