Home 198. House Robber
Post
Cancel

198. House Robber

Leetcode #198


題目描述

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.

白話文運動

給定一個數列 nums,其中元素代表每戶家庭所藏有的金錢數量。

請回傳在今晚你能偷到的最多的金錢數量是多少

限制:若同時搶奪連續兩戶的金錢,將觸發警鈴,那麼就無法繼續偷錢了!

題目限制

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

具體測資

Case 1

1
2
3
4
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.

Case 2

1
2
3
4
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.

解題想法

概念

尋找遞迴的關係,將問題簡化成子問題,一一突破,得到最終解。

每個小偷在當前的家門口,總是有兩個選擇:

  • 決定搶這戶 (i) 吧!那麼,代表除了 i-1 這戶無法搶奪之外,i-2之前獲得的戰利品都可以保留著。
  • 決定不搶這戶 (i)!那麼,代表 i-1 之前獲得的戰利品都可以留在手上。

因此,這時候我們只需比較這兩種選擇,哪一個拿到的錢更多。

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

實際解題

Recursive (top-down)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def rob(self, nums: List[int]) -> int:
        
        def rob_sub(i: int) -> int:
            if i < 0: 
                return 0
            return max(nums[i]+rob_sub(i-2), rob_sub(i-1))

        n = len(nums)
        return rob_sub(n-1)

Recursive + Memo (top-down)

上述方法會重複計算許多次相同的i,可以優化時間複雜度!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def rob(self, nums: List[int]) -> int:

        def rob_sub(i: int) -> int:
            if i < 0:
                return 0
            if i in self.memo:
                return self.memo[i]
            res = max(nums[i]+rob_sub(i-2), rob_sub(i-1))
            self.memo[i] = res
            return res
        
        n = len(nums)
        self.memo = dict()
        return rob_sub(n-1)

  • 時間複雜度:O(N)
  • 空間複雜度:O(N)

Iterative + memo (bottom-up)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rob(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        if n < 1:
            return 0
        
        if n == 1:
            return nums[0]
        
        memo = [0] * n
        memo[0] = nums[0]
        memo[1] = max(nums[0], nums[1])
        
        for i in range(2, n):
            memo[i] = max(memo[i-2]+nums[i], memo[i-1])
        
        return memo[-1]
  • 時間複雜度:O(N)
  • 空間複雜度:O(N)

Iterative + N variables (bottom-up)

我們可以注意到我們僅需使用到 memo[i-2]memo[i-1] 的數值,不需要去創建一個長度為 nmemo,因此可以優化空間複雜度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob(self, nums: List[int]) -> int:
        
        n = len(nums)

        if n < 1:
            return 0
        
        if n == 1:
            return nums[0]
        
        prev1 = 0
        prev2 = 0
        for num in nums:
            tmp = prev1
            prev1 = max(num+prev2, prev1)
            prev2 = tmp
        return prev1
  • 時間複雜度:O(N)
  • 空間複雜度:O(1)

複雜度分析

請參照上方各解法之細節。


討論區

這篇完美解析 DP 的問題,希望自己也能循序解決類似的問題!

This post is licensed under CC BY 4.0 by the author.