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

intnum1[10001];//用于統(tǒng)計(jì)每個(gè)數(shù)字的總和（數(shù)字×出現(xiàn)次數(shù)）

Solution(){

//初始化統(tǒng)計(jì)數(shù)組

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

num1[i]=0;

}

}

intdeleteAndEarn(vector<int>&nums){

//統(tǒng)計(jì)每個(gè)數(shù)字的總和

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

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

}

intdp[10001];//dp數(shù)組，dp[i]表示處理到數(shù)字i時(shí)的最大點(diǎn)數(shù)

dp[0]=num1[0];//只有數(shù)字0的情況

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

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

intdpmax=dp[2];//記錄當(dāng)前最大值

代碼實(shí)現(xiàn)

//動(dòng)態(tài)規(guī)劃遞推

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

//當(dāng)前數(shù)字可以選擇的前提是前一個(gè)數(shù)字沒有被選

//所以可以從i-2或i-3轉(zhuǎn)移過來

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

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

}

returndpmax;

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