這道題和第 198 題相似，建議讀者首先閱讀「198. 打家劫舍」

🔒LeetCode之打家劫舍Ⅰ：LeetCode之打家劫舍Ⅰ

---

1.打家劫舍II 題目描述

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 。

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

💎示例 1：

輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。

💎示例 2：

輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）。
偷竊到的最高金額 = 1 + 3 = 4 。

💎示例 3：

輸入：nums = [0]
輸出：0

📜提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

---

2.打家劫舍Ⅱ思路分析

🔗直達打家劫舍①鏈接，默認讀者已經(jīng)搞懂了打家劫舍①.

該問題是在打家劫舍①的基礎(chǔ)上，添加了一個循環(huán)結(jié)構(gòu)。如果你已經(jīng)理解了打家劫舍①，那么這個Ⅱ只需要考慮怎么解決這個循環(huán)問題即可，也就是第一個數(shù)據(jù)和最后一個數(shù)據(jù)不能同時出現(xiàn)，要么最大金額只包含第一個數(shù)據(jù)，要么只包含最后一個數(shù)據(jù)。

所以我們可以將數(shù)組分為兩部分，各自找出每一部分的最大金額，然后返回它們兩個金額最大的即可【你會發(fā)現(xiàn)這樣分為兩部分之后，就不會出現(xiàn)第一個和最后一個數(shù)據(jù)同時出現(xiàn)的問題了；然后每一部分的解題過程就和打家劫舍1一模一樣了。

---

3.暴力解法-遞歸實現(xiàn)

📕流程

（1）將數(shù)組分為兩部分即可

• 0 ~ n - 1
• 1 ~ n

（2）然后將每一部分按照打家劫舍Ⅰ求解即可
（3）返回這兩部分結(jié)果的最大值

public int rob(int[] nums) {int l = nums.length;if (l == 1) {return nums[0];}if (l == 2) {return Math.max(nums[0], nums[1]);}int[] preNums = new int[l - 1];int[] sufNums = new int[l - 1];for (int i = 0; i < l - 1; i++) {preNums[i] = nums[i];if (i > 0) {sufNums[i - 1] = nums[i];}}sufNums[l - 2] = nums[l - 1];//以上代碼是將數(shù)組分為兩個子數(shù)組【1~n,0~n-1】preNums[1] = Math.max(preNums[0], preNums[1]);sufNums[1] = Math.max(sufNums[0], sufNums[1]);//以上兩行與打家劫舍1類似return Math.max(recursion(preNums.length - 1, preNums), recursion(sufNums.length - 1, sufNums));}public int recursion(int n, int[] nums) {if (n == 0 || n == 1) {return nums[n];}return Math.max(recursion(n - 1, nums), recursion(n - 2, nums) + nums[n]);}

當(dāng)我將該暴力解法提交到LeetCode，發(fā)現(xiàn)會超時。


從上圖我們可以看出使用遞歸出現(xiàn)了大量的重復(fù)計算（我只是枚舉前三行，越往后重復(fù)越多），這是遞歸比較忌諱的問題之一（重復(fù)和棧溢出）。這樣無異于在浪費CPU的運算單元。

復(fù)雜度分析：
空間復(fù)雜度：O(n)【每個棧空間復(fù)雜度為O(1)】O(n*1)=O(n)
時間復(fù)雜度：O(n^n)

• 遞歸算法的空間復(fù)雜度與所生成的最大遞歸樹的深度成正比。如果遞歸算法的每個函數(shù)調(diào)用都占用 O(m) 空間,并且如果遞歸樹的最大深度為 n,則遞歸算法的空間復(fù)雜度將為 O(n·m)。”

💌上述中遞歸解題方式的缺點就是重復(fù)量比較多，所以我們可以可以將途中計算的結(jié)果保存下來，俗稱記憶集或記憶化搜索。此時你應(yīng)該想到這不正是動態(tài)規(guī)劃嘛。

---

4.記憶化搜索-動態(tài)規(guī)劃

需要兩個dp數(shù)組進行保存，因為在抽象層面分為兩個數(shù)組了嘛，所以要使用兩個記憶集。其他就和打家劫舍1一樣了。

循環(huán)體內(nèi)部包含兩部分

• 0 ~ n-1
• 1 ~ n

public int rob2(int[] nums) {if (nums.length == 1) {return nums[0];}if (nums.length == 2) {return Math.max(nums[0], nums[1]);}int[] dp1 = new int[nums.length - 1];dp1[0] = nums[0];dp1[1] = Math.max(nums[0], nums[1]);int[] dp2 = new int[nums.length - 1];dp2[0] = nums[1];dp2[1] = Math.max(nums[1], nums[2]);for (int i = 2; i < nums.length - 1; i++) {//0~n-1dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);//1~ndp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);}return Math.max(dp1[nums.length - 2], dp2[nums.length - 2]);}

復(fù)雜度分析

空間復(fù)雜度為O(n)
時間復(fù)雜度為O(n)

當(dāng)我提交LeetCode上時，可以發(fā)現(xiàn)通過了。
分析一下：能不能將空間復(fù)雜度優(yōu)化成O(1)呢？

---

5.動態(tài)規(guī)劃之優(yōu)化空間復(fù)雜度

如果理解了打家劫舍1和前面的流程，這個應(yīng)該很簡單。

public int rob3(int[] nums) {if (nums.length == 1) {return nums[0];}if (nums.length == 2) {return Math.max(nums[0], nums[1]);}int pre1 = nums[0], pre2 = nums[1];int suf1 = Math.max(nums[0], nums[1]);int suf2 = Math.max(nums[1], nums[2]);int maxMoney1 = suf1;int maxMoney2 = suf2;for (int i = 2; i < nums.length - 1; i++) {maxMoney1 = Math.max(pre1 + nums[i], suf1);pre1 = suf1;suf1 = maxMoney1;maxMoney2 = Math.max(pre2 + nums[i + 1], suf2);pre2 = suf2;suf2 = maxMoney2;}return Math.max(maxMoney1, maxMoney2);}

復(fù)雜度分析

時間復(fù)雜度：O(n）
空間復(fù)雜度：O(1)

提交到LeetCode，當(dāng)然能通過

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】LeetCode之打家劫舍Ⅱ——暴力递归+动态规划解决循环问题+DP空间优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。