0213. House Robber II (Medium)

Question

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and ** it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police .

Example 1

1
2
3
4
5

Input: [2,3,2]
Output: 3
Explanation:
You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.

Example 2

1
2
3
4
5

Input: [1,2,3,1]
Output: 4
Explanation:
Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

分析/解題

繼上一次偷完一排房子 以後，我們決定挑戰更高難度的偷竊XD
(有完沒完啦！)

保全狀態依舊是相鄰房子連續被偷就會響警報，不同的是，
現在房子的分布是圓形！也就是第一間和最後一間是相鄰的，
這就會造成我們上一次使用的算法會出現問題。

那麼怎麼辦呢？
第一間和最後一間有關聯是不是？
那我們就來斷開魂結，斷開鎖鏈，斷開一切的牽連吧！(大誤)

這裡我們為求方便起見，使用0為index開頭來描述，
這樣等一下對照程式碼也比較方便。
我們令nums的總長度為l ，
並且使用dp[i] 來表示偷到index i的房子時當前所能得到的最大金額。

如何處理index 0跟l-1的關係呢？
針對index 0的話，只會分成偷 或不偷 。

古語有云：

To rob, or not to rob, that is a question.

• 莎士比亞沒有說過

所以我們可以分開來討論。
假設今天無論如何就是要偷index 0 的房子的話，
可以得到以下推論：

1. index l-1不能偷
2. dp[0] = nums[0], dp[1] = nums[0] (偷了0就不能偷1)
3. 這狀況能得到的最大金額應為dp[l-2] (因l-1不能偷)
   這個狀況，我們可以給定2的起始條件並計算到dp[l-2]即可得到最大金額。

假設今天就是不偷index 0的房子的話，
可以得到以下推論：

1. index l-1能不能偷只需要看index l-2 決定要不要偷
2. dp[0] = 0, dp[1] = nums[1] (因0不偷，dp[1]要選擇偷index 1)
3. 這狀況能得到的最大金額應為dp[l-1]

所以依照這兩個狀況拆開來分別計算一次，
將兩個結果比較大小，取較大的即為答案。

同上一題描述的一樣，
我們可以利用兩個變數及一個暫存變數，來達到dp的效果。

Java

Python的部分則再額外提供了將迴圈部分包裝成函式的程式碼，
但實測上由於需要呼叫的原因，看起來平均會略慢於未包裝的狀況。
(附在底下註解處，使用者可再多執行幾次試試看)

Python

所以總體而言，這題的根本在於，當發現有些狀態是互相關聯時，
嘗試將其進行拆解，從而重新得到線性可計算動態規劃的狀態。 再次強調， DP的精髓在於找到初始狀態，
及找到從一個狀態推展到下一個狀態的方法。用骨牌來比喻的話，後者相當於 骨牌之間的關係，
前者則相當於那個第一個倒下來的骨牌 。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1)
這次的範例程式碼已經不用dp陣列來記錄了，
即便需要掃過nums兩次，但時間複雜度還是O(N))

「如果保安增強，變成只要連續三棟房子內任二棟被偷即會有警報的話？」
(可以嘗試用類似的方式來推導)

相似及延伸

1. 0337. House Robber III 2.0746. Min Cost Climbing Stairs

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~