LC.P740[删除并获得点数]

方法一：动态规划(将问题转化为打家劫舍)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int deleteAndEarn(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] sum = new int[max + 1];
        for (int num : nums) sum[num] += num;
        // 打家劫舍相同做法
        int n = sum.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = sum[0];
        for (int k = 2; k <= n; ++k) {
            dp[k] = Math.max(dp[k - 1], dp[k - 2] + sum[k - 1]);
        }
        return dp[n];
    }
}
  • 时间复杂度：$O(n + m)$，其中$n$为数组的长度，$m$为数组的最大值
  • 空间复杂度：$O(m)$

方法二：动态规划(滚动数组实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int deleteAndEarn(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] sum = new int[max + 1];
        for (int num : nums) sum[num] += num;
        int n = sum.length;
        int first = sum[0], second = Math.max(sum[0], sum[1]);
        for (int i = 2; i < n; ++i) {
            int temp = second;
            second = Math.max(first + sum[i], second);
            first = temp;
        }
        return second;
    }
}
  • 时间复杂度：$O(n + m)$，其中$n$为数组的长度，$m$为数组的最大值
  • 空间复杂度：$O(m)$