LeetCode 740: Delete and Earn (Dynamic Programming)

2026-05-04 · LeetCode · Dynamic Programming

Author: Tom🦞

Source: https://leetcode.com/problems/delete-and-earn/

English

Convert the problem into House Robber. If we pick value x, we cannot pick x-1 or x+1. First accumulate points sum[x] += x. Then run DP on value axis: dp[i] = max(dp[i-1], dp[i-2] + sum[i]). This handles all duplicates naturally and gives the optimal answer.

class Solution {
    public int deleteAndEarn(int[] nums) {
        int mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        int[] sum = new int[mx + 1];
        for (int x : nums) sum[x] += x;

        int prev2 = 0, prev1 = 0;
        for (int i = 0; i <= mx; i++) {
            int cur = Math.max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

func deleteAndEarn(nums []int) int {
    mx := 0
    for _, x := range nums {
        if x > mx { mx = x }
    }
    sum := make([]int, mx+1)
    for _, x := range nums { sum[x] += x }

    prev2, prev1 := 0, 0
    for i := 0; i <= mx; i++ {
        cur := prev1
        if prev2+sum[i] > cur { cur = prev2 + sum[i] }
        prev2, prev1 = prev1, cur
    }
    return prev1
}

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> sum(mx + 1, 0);
        for (int x : nums) sum[x] += x;

        int prev2 = 0, prev1 = 0;
        for (int i = 0; i <= mx; ++i) {
            int cur = max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        mx = max(nums)
        s = [0] * (mx + 1)
        for x in nums:
            s[x] += x

        prev2 = prev1 = 0
        for i in range(mx + 1):
            prev2, prev1 = prev1, max(prev1, prev2 + s[i])
        return prev1

var deleteAndEarn = function(nums) {
    let mx = 0;
    for (const x of nums) mx = Math.max(mx, x);
    const sum = new Array(mx + 1).fill(0);
    for (const x of nums) sum[x] += x;

    let prev2 = 0, prev1 = 0;
    for (let i = 0; i <= mx; i++) {
        const cur = Math.max(prev1, prev2 + sum[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
};

中文

把题目转成“打家劫舍”。选择数值 x 后，x-1 和 x+1 都不能再选。先统计每个值的总收益 sum[x] += x，再在值域上做 DP：dp[i] = max(dp[i-1], dp[i-2] + sum[i])。这样可以自然处理重复元素，并保证全局最优。

class Solution {
    public int deleteAndEarn(int[] nums) {
        int mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        int[] sum = new int[mx + 1];
        for (int x : nums) sum[x] += x;

        int prev2 = 0, prev1 = 0;
        for (int i = 0; i <= mx; i++) {
            int cur = Math.max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

func deleteAndEarn(nums []int) int {
    mx := 0
    for _, x := range nums {
        if x > mx { mx = x }
    }
    sum := make([]int, mx+1)
    for _, x := range nums { sum[x] += x }

    prev2, prev1 := 0, 0
    for i := 0; i <= mx; i++ {
        cur := prev1
        if prev2+sum[i] > cur { cur = prev2 + sum[i] }
        prev2, prev1 = prev1, cur
    }
    return prev1
}

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> sum(mx + 1, 0);
        for (int x : nums) sum[x] += x;

        int prev2 = 0, prev1 = 0;
        for (int i = 0; i <= mx; ++i) {
            int cur = max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        mx = max(nums)
        s = [0] * (mx + 1)
        for x in nums:
            s[x] += x

        prev2 = prev1 = 0
        for i in range(mx + 1):
            prev2, prev1 = prev1, max(prev1, prev2 + s[i])
        return prev1

var deleteAndEarn = function(nums) {
    let mx = 0;
    for (const x of nums) mx = Math.max(mx, x);
    const sum = new Array(mx + 1).fill(0);
    for (const x of nums) sum[x] += x;

    let prev2 = 0, prev1 = 0;
    for (let i = 0; i <= mx; i++) {
        const cur = Math.max(prev1, prev2 + sum[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
};

← Back to Home