力扣740題「刪除并獲得點數(shù)」新手教程

力扣740題「刪除并獲得點數(shù)」新手教程一題目重新分析與解讀題目描述：給定一個整數(shù)數(shù)組nums，你可以對它進(jìn)行一些操作。每次操作中，選擇任意一個nums[i]，刪除它并獲得nums[i]的點數(shù)。但之后必須刪除所有等于nums[i]-1和nums[i]+1的元素。重復(fù)這個過程直到?jīng)]有元素可以刪除為止。返回你能通過這些操作獲得的最大點數(shù)。難點解析?：刪除一個數(shù)后，相鄰數(shù)會被刪除，這類似于"不能選擇相鄰元素"的問題需要權(quán)衡：選擇某個數(shù)能獲得多少點數(shù)，但會失去相鄰數(shù)的點數(shù)題目本質(zhì)上是"打家劫舍"問題的變種，但需要先對數(shù)字進(jìn)行統(tǒng)計處理現(xiàn)實生活場景類比想象你是一個果園主人，果園里有不同種類的果樹（數(shù)字代表果樹種類，數(shù)量代表該種類果樹的產(chǎn)量）。你可以選擇收獲某一種果樹的所有果實（獲得點數(shù)），但這樣做會導(dǎo)致相鄰種類的果樹（數(shù)字±1）全部被砍掉（不能再收獲）。你需要規(guī)劃收獲順序，使總收獲量最大。例如：果園有：蘋果樹(3)2棵、梨樹(4)3棵、桃樹(5)1棵如果收獲梨樹：得到4×3=12點，但蘋果樹和桃樹都不能再收獲如果收獲蘋果樹和桃樹：得到3×2+5×1=11點顯然第一種方案更優(yōu)解題步驟詳解統(tǒng)計數(shù)字總和?：創(chuàng)建一個數(shù)組，統(tǒng)計每個數(shù)字出現(xiàn)的總和（數(shù)字×出現(xiàn)次數(shù)）初始化動態(tài)規(guī)劃數(shù)組?：dp[i]表示處理到數(shù)字i時能獲得的最大點數(shù)處理前幾個特殊情況?：dp[0]：只有數(shù)字0時的最大點數(shù)dp[1]：數(shù)字0和1中較大的那個dp[2]：數(shù)字0+2或數(shù)字1中的較大值動態(tài)規(guī)劃遞推?：對于i≥3，dp[i]=max(dp[i-2]+當(dāng)前數(shù)字總和,dp[i-3]+當(dāng)前數(shù)字總和)尋找最大值?：因為最大點數(shù)不一定在最后，需要記錄過程中的最大值注意事項數(shù)字范圍：題目中數(shù)字范圍是1到10000，所以數(shù)組大小要足夠邊界條件：處理dp[0]、dp[1]、dp[2]時需要特別小心空間優(yōu)化：可以使用滾動數(shù)組來優(yōu)化空間復(fù)雜度時間優(yōu)化：可以只處理實際出現(xiàn)的數(shù)字范圍，而不是0-10000初始化：統(tǒng)計數(shù)組和dp數(shù)組都需要正確初始化代碼實現(xiàn)與注釋classSolution{public:intnum1[10001];//用于統(tǒng)計每個數(shù)字的總和（數(shù)字×出現(xiàn)次數(shù)）Solution(){//初始化統(tǒng)計數(shù)組for(inti=0;i<10001;i++){num1[i]=0;}}intdeleteAndEarn(vector<int>&nums){//統(tǒng)計每個數(shù)字的總和for(inti=0;i<nums.size();i++){num1[nums[i]]+=nums[i];}intdp[10001];//dp數(shù)組，dp[i]表示處理到數(shù)字i時的最大點數(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或選1intdpmax=dp[2];//記錄當(dāng)前最大值//動態(tài)規(guī)劃遞推for(inti=3;i<10001;i++){//當(dāng)前數(shù)字可以選擇的前提是前一個數(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;}};問題與代碼分析問題分析?：這道題本質(zhì)上是動態(tài)規(guī)劃問題，與經(jīng)典的"打家劫舍"問題類似。關(guān)鍵點在于：將原始問題轉(zhuǎn)化為"不能選擇相鄰數(shù)字"的問題預(yù)處理數(shù)字，統(tǒng)計每個數(shù)字的總和使用動態(tài)規(guī)劃找到最優(yōu)解代碼分析?：預(yù)處理階段?：使用num1數(shù)組統(tǒng)計每個數(shù)字的總和，這一步將問題轉(zhuǎn)化為類似"打家劫舍"問題初始化階段?：處理前幾個特殊情況，為動態(tài)規(guī)劃建立基礎(chǔ)動態(tài)規(guī)劃階段?：通過狀態(tài)轉(zhuǎn)移方程逐步計算每個數(shù)字的最優(yōu)解最大值記錄?：因為最優(yōu)解不一定出現(xiàn)在最后，需要記錄過程中的最大值優(yōu)化建議?：可以只處理實際出現(xiàn)的數(shù)字范圍，而不是0-10000，減少循環(huán)次數(shù)可以使用滾動數(shù)組，將空間復(fù)雜度從O(n)降到O(1)可以預(yù)處理找出n