0198. House Robber (Easy)

Question

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that 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: [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.

Example 2

1
2
3
4
5

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

分析/解題

題目描述你是一個專業的強盜，即將進行入室行竊的勾當。
每間房子都存有確定數量的金錢，但唯一的限制是，每間房都有安保設置，只要相鄰的二間房子在同一個晚上被闖入的話，系統就會自動報警。
給定一個用來表示每間房子存放金額的陣列，試求在不驚動警察狀況下，
最大可以獲得的金額。

看到這個問題的時候，首先就想OS: 一間就報警的話不是最乾脆XD

好吧，我們假設這個安保真的是有這種漏洞的話，
那麼怎麼偷最好呢？

由於題目條件的限制，我們先假設一路偷到第i間，
所能獲得的最大金額為rob[i]，rob[i]會受到什麼限制呢？
假設我們走到第i間，
選擇要偷第i間的話，意味著我們前面不能偷第i-1間 。
這種狀況下，我們可以將rob[i]的值拆開來算：
rob[i] = rob[i-2] + num[i]
(選擇不動第i-1間，並偷了第i間，
而在此之前i-2間所能偷到的最大值是rob[i-2])

那麼，選擇不偷第i間的話，意味著rob[i] = rob[i-1] (因為你沒偷嘛XD)

既然有這兩種可能，那麼我們就該選當中比較大的，
所以rob[i] = max(rob[i-1], rob[i-2] + nums[i]) 。

讓我們考慮一下最前面的狀況：
rob[0] = nums[0] (第一間不用考慮前面的影響)
rob[1] = max(nums[0], nums[1]) (兩間選一間偷)

所以接下來我們只需要一路用前面的式子，迴圈從i=2計算到i=n-1，
最後將rob[n-1]回傳即可。

所以一路下來，讀者會發現有關動態規劃的題目，
一直在做的事情其實就是嘗試尋找在第n項的解，
和前面的項次之間的關係，一旦能找到這個關係，
並能確認初始的條件，就能一路從頭開始計算將其解出。

在程式碼的部分，我們可以先行考慮nums為空跟長度為1的狀況，
直接回傳結果以節省空間。

Java

Python

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

「時間/空間複雜度？」
(O(N), O(N)，掃過一次nums陣列，
並且也用相同長度來儲存最大的偷取金額)

「空間複雜度可以降低嗎？」
(可以！可以觀察出每個rob的值之間的關聯只有和前2個值有關(i-2和i-1)
我們可以使用robprev, robnext搭配一個temp值，
在迴圈中使用類似下面的方式，可以反復更新值，如此一來，
就只需要O(1)的空間就可以解決此題。)

1
2
3

int tmp = robprev;
robprev = robnext;
robnext = Math.max(robprev, tmp + nums[i]);

相似及延伸

1.0213. House Robber II (Medium) (從線性變圓形) 2. 0337. House Robber III (Medium) (變成二元樹 )
(到底哪個鄉鎮會這樣子蓋房子啦XD)

Special Thanks suggestions/corrections from viewers:

From Medium:

Raiy Kuo - 更正Python程式碼尾端，應回傳rob[-1]或rob[l-1]即可。
(歡迎提供意見協助更正歐~)

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