LeetCode 740. 删除并获得点数

Categories:

题目描述
思路分析
1. 解法一：转化为打家劫舍（推荐）
相似题目

题目描述

✅ 740. 删除并获得点数

思路分析

解法一：转化为打家劫舍（推荐）

核心思路：

将相同数字的收益累加，得到每个数值 x 的总收益 sum[x]。

若选择 x，则不能选择 x-1 和 x+1，等价于打家劫舍问题。

线性 DP：take = skip + sum[x]，skip = max(skip, take)。

复杂度分析：

时间复杂度：O(M)，其中 M 表示数值最大值。

空间复杂度：O(M)，用于存储收益数组。

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] sum = new int[maxVal + 1];
        for (int num : nums) {
            sum[num] += num;
        }

        int take = 0;
        int skip = 0;
        for (int i = 0; i <= maxVal; i++) {
            int takeNew = skip + sum[i];
            int skipNew = Math.max(skip, take);
            take = takeNew;
            skip = skipNew;
        }

        return Math.max(take, skip);
    }
}

func deleteAndEarn(nums []int) int {
	maxVal := 0
	for _, v := range nums {
		if v > maxVal {
			maxVal = v
		}
	}

	sum := make([]int, maxVal+1)
	for _, v := range nums {
		sum[v] += v
	}

	take, skip := 0, 0
	for i := 0; i <= maxVal; i++ {
		takeNew := skip + sum[i]
		skipNew := skip
		if take > skipNew {
			skipNew = take
		}
		take, skip = takeNew, skipNew
	}

	if take > skip {
		return take
	}
	return skip
}

相似题目

题目	难度	考察点
198. 打家劫舍	中等	动态规划
213. 打家劫舍 II	中等	动态规划
337. 打家劫舍 III	中等	动态规划
256. 粉刷房子	中等	动态规划
746. 使用最小花费爬楼梯	简单	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/46642799