删除并获得点数

Delete and Earn

问题：删除并获得点数

考察：数组、哈希表、动态规划

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/delete-and-earn

Problem: Delete and Earn

Patterns: Array, Hash Table, Dynamic Programming

Recency: 2yr

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

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：把相同数字的贡献合并成 points[x] = x * count[x]。选择 x 就不能选择 x-1 和 x+1，问题转化为 House Robber，在数值轴上做动态规划。

复杂度：设最大值为 M，时间 O(n+M)，空间可 O(M) 或排序后 O(u)。