這一篇是上一篇的擴展，需要針對特殊情況特殊考慮，當然其本質還是動態規劃。
原題
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味著第一個房屋和最後一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例 1:
<code>輸入:
[2,3,2]
輸出:
3
解釋:
你不能先偷竊
1
號房屋（金額
=
2
），然後偷竊
3
號房屋（金額
=
2
）,
因為他們是相鄰的。
/<code>
示例 2:
<code>輸入:
[1,2,3,1]
輸出:
4
解釋:
你可以先偷竊
1
號房屋（金額
=
1
），然後偷竊
3
號房屋（金額
=
3
）。
偷竊到的最高金額
=
1
+
3
=
4
。
/<code>
原題url：
https://leetcode-cn.com/problems/house-robber-ii/
解題
這道題的變化是，同樣是一個數組，但是首尾相連了，也就是成了一個環，那麼原本遞推的方式也就行不通了，因為任何一個節點其實地位都相等了，也就找不到最初的狀態，無法進行遞推了。
但我們可以將現在的問題轉化成我們已經解決的問題，仔細想想。所謂的首尾相連，針對狀態進行劃分，可以有三種情況：
- 首尾節點都不選擇
- 只選擇首節點，不選擇尾結點
- 只選擇尾結點，不選擇首節點
因為我們最終是要求出最大值，那麼只需要考慮後面兩種情況，而這樣的話，又可以轉化成了原本的線性數組了。
接下來讓我們看看代碼：
<code>class
Solution
{public
int
rob
(
int
[] nums) {if
(nums.length ==0
) {return
0
; }if
(nums.length ==1
) {return
nums[0
]; }return
Math.max( calMax(nums,0
, nums.length -2
), calMax(nums,1
, nums.length -1
) ); }public
int
calMax
(
int
[] nums,int
start,int
end) {int
current =0
;int
next_1 =0
;int
next_2 =0
;for
(int
i = end; i >= start; i--) { current = Math.max( next_1, nums[i] + next_2 ); next_2 = next_1; next_1 = current; }return
current; } }/<code>
提交OK。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要還是利用動態規劃，只是需要大家進行思路轉化，將未知轉化為 已知，從而解決問題。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
