力扣198題（打家劫舍）教程：動態(tài)規(guī)劃解法題目要求：給定一個非負整數(shù)數(shù)組nums，代表每間房屋存放的金額。小偷計劃偷竊這些房屋，但相鄰房屋裝有防盜系統(tǒng)，若同時偷竊相鄰房屋會觸發(fā)警報。計算在不觸發(fā)警報的情況下，能偷到的最高金額。關(guān)鍵點解析："相鄰房屋不能同時偷"：必須保證每次偷竊的房屋不相鄰，即不能連續(xù)偷。動態(tài)規(guī)劃的核心：需要將問題拆解為子問題，并通過子問題的解推導(dǎo)出原問題的解。決策點：每間房屋都有兩種選擇：偷（rob）或不偷（notrob）。選擇取決于前一次的選擇，以及當(dāng)前房屋的金額。難點：如何確定狀態(tài)轉(zhuǎn)移方程，即如何通過前幾個狀態(tài)計算當(dāng)前狀態(tài)的最大金額。需要明確每次選擇對后續(xù)的影響。想像一下想象你是一個小偷，面對一條街上的房屋，每間房屋有一定現(xiàn)金。你只能偷不相鄰的房屋，否則會被抓。例如，如果偷了第1間和第3間，就能獲得兩家的金額，但第2間不能偷。你需要規(guī)劃一條路線，最大化總金額?，F(xiàn)實中的策略：每次決定偷一間房時，必須放棄前一間房（否則觸發(fā)警報），因此需要比較“偷當(dāng)前房+跳過前一間”和“不偷當(dāng)前房”兩種情況的收益，取最大值。解題步驟定義狀態(tài)：用dp[i]表示前i間房屋能偷到的最高金額。邊界條件：若只有1間房（i=1），則dp[1]=nums[0]（只能偷這間）。若有2間房（i=2），則dp[2]=max(nums[0],nums[1]）（選擇金額較大的那間）。3.遞推公式：對于第i間房，有兩種選擇：偷第i間：此時不能偷第i-1間，收益為dp[i]=nums[i]+dp[i-2]（前i-2間的最高金額）。不偷第i間：收益為dp[i]=dp[i-1]（前i-1間的最高金額）。因此，遞推公式為：dp[i]=max(nums[i]+dp[i-2],dp[i-1])。4.循環(huán)計算：從i=3開始，依次計算dp[3]、dp[4]...dp[n]，每個dp[i]利用前兩個狀態(tài)的值。5.返回結(jié)果：最終需要的是dp[n]，即前n間房的最高金額。注意事項邊界條件處理：用戶代碼中手動處理了n=1、2、3的情況，但需要確保邏輯正確。例如，n=3時應(yīng)比較nums[0]+nums[2]和nums[1]，而不是直接賦值dp[2]。狀態(tài)轉(zhuǎn)移的正確性：用戶代碼中的dp[i]=max(dp[i-2]+nums[i],dp[i-3]+nums[i-1])是錯誤的，因為dp[i-3]和nums[i-1]對應(yīng)的是相鄰房屋，違反了題目規(guī)則。正確公式應(yīng)為dp[i]=max(dp[i-2]+nums[i],dp[i-1])。數(shù)組越界問題：用戶定義的dp[100]固定大小，若nums長度超過100會導(dǎo)致錯誤。應(yīng)使用動態(tài)數(shù)組或確保循環(huán)范圍正確?？臻g優(yōu)化：動態(tài)規(guī)劃可優(yōu)化至O(1)空間，僅用兩個變量存儲前兩個狀態(tài)，避免數(shù)組開銷。特殊情況：若nums為空或長度為0，應(yīng)返回0。添加代碼并注釋classSolution{public:introb(vector<int>&nums){//邊界條件處理if(nums.size()==0)return0;//空數(shù)組，返回0if(nums.size()==1)returnnums[0];//1間房，直接偷if(nums.size()==2)returnmax(nums[0],nums[1]);//2間房，選金額大的//動態(tài)規(guī)劃數(shù)組（或滾動變量優(yōu)化，此處用數(shù)組示意）intdp[100];dp[0]=nums[0];//第1間房的金額dp[1]=max(nums[0],nums[1]);//前2間房的最大金額for(inti=2;i<nums.size();i++){//從第3間房開始計算//狀態(tài)轉(zhuǎn)移方程：選擇偷或不偷當(dāng)前房dp[i]=max(nums[i]+dp[i-2],dp[i-1]);//nums[i]+dp[i-2]：偷當(dāng)前房+前i-2間房的金額//dp[i-1]：不偷當(dāng)前房，繼承前i-1間的金額}returndp[nums.size()-1];//返回前n間房的最大金額}};分析空間優(yōu)化：由于每次僅依賴dp[i-1]和dp[i-2]，可用兩個變量（如pre1、pre2）滾動更新，代碼改為：時間復(fù)雜度：O(n)，循環(huán)n次?？臻g復(fù)雜度：O(1)或O(n)（取決于是否使用數(shù)組）。錯誤排查技巧：若結(jié)果不正確，檢查邊界條件（如n=1、2、3的情況）。模擬遞推過程，手寫dp數(shù)組的前幾步驗證狀態(tài)轉(zhuǎn)移是否正確。例如，輸入[1,2,3,1]，dp應(yīng)為[1,2,3,4]，最終結(jié)果應(yīng)為4（偷1、3、4號房）?？偨Y(jié)：力扣198題的核心