DeleteAndEarn740

[underwindfall]

• https://leetcode-cn.com/problems/delete-and-earn/

• 思路

  • 389 #388 #387

• [ ] 刷15mins

• [ ] 刷5mins

 // time O(n +k)
    // space O(n + k)
    class TopDown {
        public int deleteAndEarn(int[] nums) {
            int[] buckets = new int[10001];
            for (int num : nums) {
                buckets[num] += num;
            }

            int[] dp = new int[10001];
            dp[0] = buckets[0];
            dp[1] = buckets[1];
            for (int i = 2; i < buckets.length; i++) {
                dp[i] = Math.max(buckets[i] + dp[i - 2], dp[i - 1]);
            }
            return dp[10000];
        }
    }

    // time O(n +k)
    // space O(n + k)
    class TopDownOfficial {
        class Solution {
            private Map<Integer, Integer> points = new HashMap<>();
            private Map<Integer, Integer> cache = new HashMap<>();

            private int maxPoints(int num) {
                // Check for base cases
                if (num == 0) {
                    return 0;
                }

                if (num == 1) {
                    return points.getOrDefault(1, 0);
                }

                if (cache.containsKey(num)) {
                    return cache.get(num);
                }

                // Apply recurrence relation
                int gain = points.getOrDefault(num, 0);
                cache.put(num, Math.max(maxPoints(num - 1), maxPoints(num - 2) + gain));
                return cache.get(num);
            }

            public int deleteAndEarn(int[] nums) {
                int maxNumber = 0;

                // Precompute how many points we gain from taking an element
                for (int num : nums) {
                    points.put(num, points.getOrDefault(num, 0) + num);
                    maxNumber = Math.max(maxNumber, num);
                }

                return maxPoints(maxNumber);
            }
        }
    }