一、博客聲明

??找工作逃不過刷題，為了更好的督促自己學(xué)習(xí)以及理解力扣大佬們的解題思路，開辟這個系列來記錄。代碼可能不是自己寫的，不求方法最好，只求更多地理解大佬們的解題思路。

---

二、題目描述

??你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

---

三、解題思路

1、線性動態(tài)規(guī)劃

?a、什么是動態(tài)規(guī)劃

??動態(tài)規(guī)劃不是一種算法，而是一種思想和解題策略。而要掌握動態(tài)規(guī)劃比較難，小編還沒有掌握，還在努力算題中。也不知道該怎么解釋。推薦大家去看下面的視頻：
??視頻1：【動態(tài)規(guī)劃】這可能是最好懂的動態(tài)規(guī)劃入門教程
??視頻2：動態(tài)規(guī)劃入門50題

2、思路說明

??換種理解方式，如果有A,B,C,D四個區(qū)域，如何保證我穿過四個區(qū)域走的路程最長？是不是就是只要保證每個區(qū)域都走最長的路，就可以保證四個區(qū)域后，我走的路程最長。
??那么打家劫舍這個題目，換個思想，只要保證我到第i家時，不管偷還是不偷，手里積累的錢是兩種策略（偷和不偷）中最多的就可以了。如果偷的話，錢就變?yōu)橥档?strong>前前一家積累的錢加上這家的錢，不偷的話就是偷到前一家積累的錢。比較這兩個誰大就可以了。然后就是保存好偷到第i-2家和偷到第i-1家積累的錢，方便對下一家是否偷作為判斷依據(jù)。
??1、如果數(shù)組長度等于1，返回nums[0]；
??2、如果數(shù)組長度等于2，返回fmax(nums[0], nums[1])；
??3、如果數(shù)組長度大于2，就需要從第三房子開始判斷，偷還是不偷這兩種選擇，哪種選擇能讓當(dāng)前手中積累的錢更多；

??打家劫舍2只需要考慮偷盜的范圍就可以了，代碼最后一行變?yōu)?code>return fmax(stealRang(nums, 0, numsSize - 2), stealRang(nums, 1, numsSize - 1));。也就是考慮第一家偷的話，最后一家就不能偷，范圍就變?yōu)閺牡?code>0家偷到numsSize-2家；如果不偷第一家，范圍就變成了從第1家偷到第numsSize-1家；比較這兩個誰大就可以了。
?

---

四、解題代碼（附注釋）

///偷竊范圍，從第start家到第end家。
int stealRang(int* nums, int start, int end){int first = nums[start], second = fmax(first, nums[start+1]);for(int i = start + 2; i <=end; i++){int temp = second;//考慮第i家，偷與不偷，哪個得的錢更多，不偷就還是原來的second值，偷就是前一家+該家金額second = fmax(second, first + nums[i]);first = temp;}return second;
}//該題目為屬于線性動態(tài)規(guī)劃題目
int rob(int* nums, int numsSize) {if(numsSize <= 1){//長度為1，返回第一個元素return nums[0];}if(numsSize == 2){//長度為2，返回兩個元素中最大的return fmax(nums[0], nums[1]);}return stealRang(nums, 0, numsSize - 1);//返回最大值//return fmax(stealRang(nums, 0, numsSize - 2), stealRang(nums, 1, numsSize - 1)); //打家劫舍2返回這個
}