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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [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:

Input: nums = [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.

解題思路:

問題主要是要找出能偷到最多錢的組合，並且不能偷相鄰的元素(房子)。

一樣可以試著遞迴或是動態規劃來解題。

拿 Example 來想想如何解題：

[1,2,3,1]

想在每個元素中都取得可以的最大值，問題是如何判斷是否偷過鄰近的房子。

最後應該拿到：

[1,2,4,4]

一開始想到的是：

  1. 陣列初始值 [1, 2, 0, 0]
  2. 從第 2 個元素開始選取當下如何找到最大值，也就是 自己 + 前前一個元素的最大值 或是 前一個元素的最大值，看這兩個哪個比較大。
  3. 就會拿到 [1, 2, 4, 0]
  4. 最後在照著 2 的規則找到最後一個元素的最大值。
  5. 最後拿到 [1, 2, 4, 4]

Code Example

def rob(nums):
    if len(nums) <= 2:
        return max(nums)
    results = [0 for i in range(len(nums))]
    results[0] = nums[0]
    # results[1] = nums[1]
    results[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        results[i] = max(results[i-1], results[i-2] + nums[i])
    print(results)
    return results[-1]

rob([2,1,1,2])

對…一開始是著麼以為的，結果發現第 1 個元素不能直接拿來用，應該拿第 0 個元素來比較。