0198. House Robber - chasel2361/leetcode GitHub Wiki

***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:
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:
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.

這個題目可以觀察出，每取出一間房子可以搶到的金額，會是現在這間跟搶到前兩間為止的總和，或是搶到前一間的總和 (因為警鈴有限制不能搶相鄰的房子)，可以觀察出以下關係。

    house[i] = max(house[i-2] + nums[i], house[i-1])

這樣的話可以得出以下程式碼：

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0: return 0
        if l == 1: return nums[0]
        house = [0] * l
        house[0] = nums[0]
        house[1] = max(nums[0], nums[1])
        for i in range(2, l):
            house[i] = max(house[i - 2] + nums[i], house[i - 1])
        return house[-1]

這樣寫的時間/空間複雜度都是 O(N)

參考了別人的寫法之後發現空間複雜度還有簡化的空間，只要利用兩個輔助變數不停更新 house 就可以了

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0: return 0
        if l <= 2: return max(nums)
        house = 0
        previous = max(nums[1], nums[0])
        m_previous = nums[0]
        for i in range(2, l):
            house = max(previous, m_previous + nums[i])
            m_previous = previous
            previous = house
        return house

這樣寫可以把空間複雜度降到 O(1)，也不用一直讀取陣列的值，速度快上不少