740. 刪除并獲得點數

中等

題目

給你一個整數數組 nums ，你可以對它進行一些操作。

每次操作中，選擇任意一個 nums[i] ，刪除它并獲得 nums[i] 的點數。之后，你必須刪除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

開始你擁有 0 個點數。返回你能通過這些操作獲得的最大點數。

示例 1：

輸入：nums = [3,4,2]
輸出：6
解釋：
刪除 4 獲得 4 個點數，因此 3 也被刪除。
之后，刪除 2 獲得 2 個點數。總共獲得 6 個點數。
示例 2：

輸入：nums = [2,2,3,3,3,4]
輸出：9
解釋：
刪除 3 獲得 3 個點數，接著要刪除兩個 2 和 4 。
之后，再次刪除 3 獲得 3 個點數，再次刪除 3 獲得 3 個點數。
總共獲得 9 個點數。

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

---

分析

這是一個非常經典的動態規劃問題，跟「打家劫舍」非常相似。

問題本質：

• 如果你選了一個數 x，你會獲得 x * 出現次數 的分數，并且不能再選 x-1 和 x+1。
• 所以你不能同時選相鄰的數（按照值排序）。
• 相當于：把所有數按照值排序，把它們看成一排房子（每個房子有一定價值），不能取相鄰的房子。

下面一步一步講解和給出代碼。

---

🟢 思路步驟

1. 統計每個數字的總價值：

   • 用一個數組 sum[x] = x * 出現次數。

   • 例如 nums = [2,2,3,3,3,4]：

     • 2出現2次，貢獻=2*2=4
     • 3出現3次，貢獻=3*3=9
     • 4出現1次，貢獻=4*1=4

2. 動態規劃：

   • 定義 dp[i]：考慮數字0~i，能取得的最大分數。

   • 轉移方程：

     dp[i] = max(dp[i-1],            // 不取idp[i-2] + sum[i]    // 取i
     )
     

   • 為什么和打家劫舍一樣？因為選了i就不能選i-1。

3. 初始化：

   • dp[0] = sum[0]
   • dp[1] = max(sum[0], sum[1])

4. 返回：

   • dp[max_value]，max_value = max(nums)

---

🟢 Python代碼

def deleteAndEarn(nums):if not nums:return 0max_num = max(nums)sum_points = [0] * (max_num + 1)# 統計每個數的總價值for num in nums:sum_points[num] += num# 動態規劃dp = [0] * (max_num + 1)dp[0] = sum_points[0]dp[1] = max(sum_points[0], sum_points[1])for i in range(2, max_num + 1):dp[i] = max(dp[i - 1], dp[i - 2] + sum_points[i])return dp[max_num]

---

🟢 示例驗證

示例1:

nums = [3,4,2]
sum_points: [0,0,2,3,4]
dp:
i=2: dp[2]=max(dp[1], dp[0]+sum[2]) = max(0,0+2)=2
i=3: dp[3]=max(dp[2], dp[1]+sum[3]) = max(2,0+3)=3
i=4: dp[4]=max(dp[3], dp[2]+sum[4]) = max(3,2+4)=6
輸出:6

示例2:

nums = [2,2,3,3,3,4]
sum_points: [0,0,4,9,4]
dp:
i=2: dp[2]=max(dp[1], dp[0]+sum[2]) = max(0,0+4)=4
i=3: dp[3]=max(dp[2], dp[1]+sum[3]) = max(4,0+9)=9
i=4: dp[4]=max(dp[3], dp[2]+sum[4]) = max(9,4+4)=9
輸出:9

?完全符合題意。

---

c++

---

🟢 C++代碼

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int deleteAndEarn(vector<int>& nums) {if (nums.empty()) return 0;int maxNum = *max_element(nums.begin(), nums.end());// sum[i] = i * 出現次數vector<int> sum(maxNum + 1, 0);for (int num : nums) {sum[num] += num;}// dp[i] = 考慮[0..i]的最大點數vector<int> dp(maxNum + 1, 0);dp[0] = sum[0];dp[1] = max(sum[0], sum[1]);for (int i = 2; i <= maxNum; ++i) {dp[i] = max(dp[i - 1], dp[i - 2] + sum[i]);}return dp[maxNum];}
};

---

🟢 用法示例

你可以這樣調用：

#include <iostream>int main() {Solution s;vector<int> nums = {2,2,3,3,3,4};cout << s.deleteAndEarn(nums) << endl;  // 輸出 9return 0;
}

---

**空間優化（O(1)空間）**

---

非常好問題！

這個DP轉移：

$$dp[i]=\max (dp[i?1],dp[i?2]+sum[i])$$

只用到了 i-1 和 i-2，所以不需要存整個數組，只需要兩個變量即可。

---

🟢 O(1)空間優化思路

• 維護兩個變量：

  • prev1：表示 dp[i-1]
  • prev2：表示 dp[i-2]

• 每次更新：

  curr = max(prev1, prev2 + sum[i]);
  

  然后：

  prev2 = prev1;
  prev1 = curr;
  

---

🟢 完整C++代碼（O(1)空間）

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int deleteAndEarn(vector<int>& nums) {if (nums.empty()) return 0;int maxNum = *max_element(nums.begin(), nums.end());vector<int> sum(maxNum + 1, 0);for (int num : nums) {sum[num] += num;}int prev2 = sum[0];                        // dp[i-2]int prev1 = max(sum[0], sum[1]);           // dp[i-1]int curr = prev1;for (int i = 2; i <= maxNum; ++i) {curr = max(prev1, prev2 + sum[i]);prev2 = prev1;prev1 = curr;}return curr;}
};

---

🟢 樣例驗證

如示例：

int main() {Solution s;vector<int> nums = {2,2,3,3,3,4};cout << s.deleteAndEarn(nums) << endl;  // 輸出 9return 0;
}

? 輸出正確。

這樣就只用 O(1) 空間，時間復雜度依然是 O(N)。

如需要，我也可以幫你寫 Java版本 或進一步優化邏輯！