力扣740題：刪除并獲得點數解題詳解06問題與代碼分析目錄01題目解析與理解02現實場景類比03解題步驟詳解04關鍵注意事項05代碼實現與注釋01題目解析與理解題目要求說明操作規則明確動態規劃適用性目標最大化點數每次選擇刪除一個元素`nums[i]`后，必須同時刪除所有值為`nums[i]-1`和`nums[i]+1`的元素，且刪除`nums[i]`時可獲得對應點數值。通過一系列操作，計算如何選擇刪除順序以獲得最大累計點數，初始點數為0。因存在重疊子問題（如刪除某數后影響后續選擇），需通過狀態轉移優化計算。若直接遍歷原數組，無法高效處理數值的相鄰關系，需先統計每個數值的總點數（如`sum[num]=numcount`）。需處理數值不連續的情況（如示例1中的`[3,4,2]`），需按數值范圍動態規劃而非原數組順序。核心問題轉化為如何避免相鄰數值的沖突選擇（類似打家劫舍問題），需通過預處理和狀態轉移方程解決。數值分布處理需定義`dp[i]`表示處理到數值`i`時的最大點數，并推導是否選擇當前數值（`dp[i]=max(dp[i-1],dp[i-2]+sum[i])`）。狀態定義與轉移邊界條件難點分析輸入輸出示例解釋示例1解析輸入：nums=[3,4,2]預處理統計：sum=[0,0,2,3,4]（數值2、3、4的總點數分別為2、3、4）。動態規劃過程：dp[2]=max(dp[1],dp[0]+2)=2dp[3]=max(dp[2],dp[1]+3)=3dp[4]=max(dp[3],dp[2]+4)=6輸出：6（刪除4后刪除2，點數累計4+2）。示例2解析輸入：nums=[2,2,3,3,3,4]預處理統計：sum=[0,0,4,9,4]（數值2出現2次，3出現3次，4出現1次）。動態規劃過程：dp[2]=max(dp[1],dp[0]+4)=4dp[3]=max(dp[2],dp[1]+9)=9dp[4]=max(dp[3],dp[2]+4)=9輸出：9（連續刪除3次3，點數累計9）。02現實場景類比數字頻率加權在本題中，每個數字的點數相當于其價值，而該數字在數組中出現的次數相當于權重。例如，數字3出現3次，則其總價值為3×3=9，這與現實中的商品單價×庫存量的價值計算邏輯完全一致。點數與價值的對應關系離散化價值分布題目要求處理不連續的數字（如2,3,4），類似于現實中不同品類商品的價值差異。需通過哈希表或數組統計每個數字的總價值，形成類似“價值-庫存”的映射表。重復數字的聚合多個相同數字可被一次性選擇并獲得其總價值，類似于批發采購場景——批量購買同一商品可獲得更高收益，但需承擔關聯風險（刪除相鄰數字）。刪除操作的現實意義選擇刪除某個數字后必須移除相鄰數字，這類似于投資中選擇某一行業時需規避其上下游關聯產業的風險。例如投資房地產需同步規避建材行業波動的影響。風險連鎖反應機會成本顯性化資源獨占性約束刪除操作本質是放棄相鄰數字的潛在收益，如同商業決策中選擇A方案必然犧牲B方案的機會成本。解題時需動態比較當前數字與相鄰數字的收益權重。每次操作后相鄰數字不可再用，類似于某些特許經營權場景——獲得某區域代理權的同時，自動喪失相鄰區域的競爭資格。動態規劃與投資組合題目中數字范圍1≤nums[i]≤10^4，可類比有限時間窗口內的任務調度。將數字按大小排序后，轉化為在時間線上選擇互不沖突的任務以最大化收益，與LeetCode1235題（規劃兼職工作）的核心思想相通。時間窗口優化博弈論中的占優策略當多個相同數字連續出現（如示例2的3,3,3），全選它們是最優策略，這類似于博弈論中的“重復博弈均衡”——在相同條件下持續執行同一策略可獲得穩定收益。通過dp數組分階段記錄歷史最大收益，類似基金經理每日調整持倉組合。dp[i]表示前i個數字的最優解，而狀態轉移方程dp[i]=max(dp[i-1],dp[i-2]+sum[i])對應“保持現狀”或“當前投入+歷史最優”的決策邏輯。最大收益的類比場景03解題步驟詳解問題轉化核心：將刪除相鄰元素約束轉化為動態規劃中「不能選擇相鄰元素」的經典問題，類似打家劫舍模型。預處理關鍵：通過桶排序思想統計數字總點數，將原始問題轉化為序列選擇問題。狀態轉移設計：dp[i]表示前i個數字能獲得的最大點數，狀態轉移時需考慮是否選擇當前數字?？臻g優化技巧：實際只需維護dp[i-1]和dp[i-2]兩個變量，可將空間復雜度從O(max_num)降至O(1)。邊界條件處理：需單獨處理數字連續區間（如[1,2,3]）和單個數字重復（如[2,2,2]）的特殊情況。性能權衡點：當max_num遠大于n時，可用哈希表替代數組存儲非零數字，減少空間消耗。解題步驟關鍵操作時間復雜度空間復雜度統計數字出現次數使用數組統計每個數字的總點數（數字×出現次數）O(n)O(max_num)初始化動態規劃數組dp[0]=num1[0],dp[1]=max(num1[0],num1[1])O(1)O(max_num)動態規劃遞推dp[i]=max(dp[i-1],dp[i-2]+num1[i])O(max_num)O(max_num)結果提取返回dp[max_num]或滾動數組最后一位O(1)O(1)邊界處理處理nums為空或單元素情況O(1)O(1)統計各數字的總和構建動態規劃數組狀態定義初始化細節空間優化定義dp數組，其中dp[i]表示前i個數字能獲得的最大點數。初始化dp[0]=0（無數字），dp[1]=sum[1]（僅選擇數字1的總和）。若數字范圍較大，可采用滾動數組優化空間，僅保留dp[i-1]和dp[i-2]的值，將空間復雜度從O(n)降至O(1)。對于連續缺失的數字（如存在數字1和3但無2），需保證dp[i]的遞推連續性，此時dp[2]應繼承dp[1]的值而非直接賦sum[2]。遞推關系建立必須從小到大遍歷數字，確保遞推時dp[i-2]和dp[i-1]已計算完成。例如處理數字i時需依賴i-1和i-2的結果。遍歷順序最終結果為dp[max_num]，其中max_num為輸入數組中的最大值。需注意遍歷結束后需比較最后兩個dp值（如max_num和max_num-1）以覆蓋所有可能情況。結果提取04關鍵注意事項數組邊界處理題目中nums[i]的取值范圍為1到10^4，因此需要預先分配足夠大的數組空間（如10001）來存儲計數和動態規劃結果，避免越界訪問。數值范圍限制空數組處理非連續數值處理雖然題目保證nums.length≥1，但實際編碼時仍需考慮動態規劃初始化階段dp[0]和dp[1]的邊界值設定，例如dp[0]=0，dp[1]=count[1]1。當輸入數組存在數值不連續（如[1,3,5]）時，動態規劃過程中需跳過未被計數的數字，直接繼承前驅狀態而非累加無效值。遞推公式的選擇狀態轉移邏輯核心遞推公式需比較"選擇當前數"和"不選當前數"兩種策略，即dp[i]=max(dp[i-1],dp[i-2]+icount[i])，其中icount[i]表示選擇i時的總收益，dp[i-2]保證不觸發相鄰數刪除懲罰。初始化條件負數處理擴展dp數組前兩個元素需顯式初始化，dp[0]對應數值0的情況（始終為0），dp[1]則取決于數字1的出現次數，即count[1]1。雖然本題無需考慮，但若擴展至含負數場景，遞推公式需增加絕對值處理或分正負數組分別計算，避免負值影響最大值判斷。123時間復雜度優化空間壓縮技巧頻次統計優化最大值剪枝由于dp[i]僅依賴前兩個狀態，可將O(n)空間優化為O(1)，僅維護prev和curr兩個變量滾動更新，大幅降低空間復雜度至常數級。預處理階段記錄數組實際最大值max_num，動態規劃只需計算到dp[max_num]而非整個10001范圍，減少無效計算次數。使用哈希表替代數組進行計數時，需按key排序后遍歷，確保動態規劃按數值遞增順序處理，避免亂序導致的邏輯錯誤。05代碼實現與注釋代碼實現classSolution{public:

intnum1[10001];//用于統計每個數字的總和（數字×出現次數）

Solution(){

//初始化統計數組

for(inti=0;i<10001;i++){

num1[i]=0;

}

}

intdeleteAndEarn(vector<int>&nums){

//統計每個數字的總和

for(inti=0;i<nums.size();i++){

num1[nums[i]]+=nums[i];

}

intdp[10001];//dp數組，dp[i]表示處理到數字i時的最大點數

dp[0]=num1[0];//只有數字0的情況

dp[1]=max(num1[0],num1[1]);//數字0和1中選較大的

dp[2]=max(num1[0]+num1[2],num1[1]);//選0+2或選1

intdpmax=dp[2];//記錄當前最大值

代碼實現

//動態規劃遞推

for(inti=3;i<10001;i++){

//當前數字可以選擇的前提是前一個數字沒有被選

//所以可以從i-2或i-3轉移過來

dp[i]=max(dp[i-2]+num1[i],dp[i-3]+num1[i]);

dpmax=max(dpmax,dp[i]);//更新最大值

}

returndpmax;

}};06問題與代碼分析算法正確性驗證動態規劃狀態轉移該問題通過構建`dp[num]=numcount[num]`的貢獻值數組，將原問題轉化為類似"打家劫舍"的相鄰元素不可同時選取問題。狀態轉移方程`max(curr,prev+dp[num])`嚴格遵循題目中"刪除nums[i]后必須刪除相鄰值"的約束條件，確保最優子結構性質。邊界條件處理算法顯式處理了空數組輸入（直接返回0），并通過`max_val=max(nums)`動態確定DP數組長度，避免預設范圍不足導致的越界錯誤。對于連續數字如[1,2,2,3]，能正確處理相鄰數字的互斥選擇邏輯。實例驗證以示例2為例，算法正確計算sum[3]=9（3個3）和sum[4]=4的取舍關系，最終輸出9符合"刪除所有3"的最優策略，驗證了狀態轉移的合理性?？臻g復雜度分析基礎DP實現原始解法使用長度為`max_val+1`的DP數組，空間復雜度為O(M)（M為nums最大值）。當輸入含大數值如1e4時，需分配1e4+1的數組空間，但題目約束nums[i]≤1e4，該復雜度在可接受范圍。哈希表優化空間滾動變量優化使用Counter統計數字頻率時，最壞情況需要O(N)空間存儲所有唯一值。對于密集數值分布（如1~M連續出現），空間會接近O(M)，但實際工程中常遠小于O(N+M)。進階解法僅維護prev和curr兩個變量，將空間壓縮至O(1)，但需注意此時仍需保留Counter的O(K)空間（K為唯一值數量），整體空間優化為O(K)而非完全常數級。123可能的優化方向離