一、博客聲明

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

---

二、題目描述

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

示例 1：

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

示例 2：

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

提示：

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

---

三、解題思路

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

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

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

2、思路說(shuō)明

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

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

---

四、解題代碼（附注釋）

///偷竊范圍，從第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家，偷與不偷，哪個(gè)得的錢(qián)更多，不偷就還是原來(lái)的second值，偷就是前一家+該家金額second = fmax(second, first + nums[i]);first = temp;}return second;
}//該題目為屬于線性動(dòng)態(tài)規(guī)劃題目
int rob(int* nums, int numsSize) {if(numsSize <= 1){//長(zhǎng)度為1，返回第一個(gè)元素return nums[0];}if(numsSize == 2){//長(zhǎng)度為2，返回兩個(gè)元素中最大的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返回這個(gè)
}