1 題目描述

有一排房子，每個房子裡面有一定的錢，但是不能連續偷兩個房子，否則會報警，在不觸發報警的狀況下求最多可以偷到多少錢。

2 解法

按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南，我很推薦把每一種步驟都嘗試寫出來看看，分別是：

  1. Step1: Recursive
  2. Step2: Recursive with Memoization
  3. Step3: Iterative + Tabulation
  4. Step4: Iterative with Constant Space

Step1: Recursive

一道很典型的通過子問題去解決原問題的題目，所以可以透過遞歸以及動態規劃解決。
假設：知道了前 n - 1 家店最多能偷的錢數，前 n - 2 家店最多能偷的錢數。
關係式：如果我們想要知道前 n 家商店最多能偷多少錢，我們可以選擇偷

  • 偷：偷第 n 家商店 + 前 n - 2 家商店最多能偷的錢數。
  • 不偷：不偷第 n 家商店 + 前 n - 1 家商店最多能偷的錢數。

最小問題：如果今天 n = 0，那麼就是0，如果n = 1，那麼就是nums[0]。

  • n = 0：表示沒有店家可以偷
  • n = 1：表示只有一家店可以偷，那也只能偷了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def rob(self, nums: List[int]) -> int:
    """
    time: O(2^n) 
    - 對於長度為 n 的數組，時間複雜度為 O(2^n)。
    - 因為每次遞歸函數都會將問題分成兩個子問題，並且繼續遞歸處理，這種情況會產生一個大小為 2^n 的遞歸樹。

    space: O(n) 遞迴的深度
    - 由於遞歸呼叫使用了函數呼叫棧，空間複雜度等於遞歸的深度。
    - 每次遞歸呼叫時，棧的深度會增加 1。最壞情況下，遞歸深度為 O(n)，因此空間複雜度為 O(n)。
    """
    n = len(nums)
    # 最小問題
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    # 偷與不偷
    steal = self.rob(nums[:-2]) + nums[-1]  # 偷：前 n - 2 家店最多能偷的錢數 + 第 n 家店
    not_steal = self.rob(nums[:-1])         # 不偷：前 n - 1 家店最多能偷的錢數
    
    # 返回最大值
    return max(steal, not_steal)

Step2: Recursive with Memoization

那我們就思考，是不是某些已經算過的子問題，我們可以直接拿來用，這樣就不用重複計算了。
因此我們需要一個dict來記錄已經算過的子問題。使用dict的好處是可以使用O(1)的時間複雜度來查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def rob2(self, nums: List[int]) -> int:
    """
    time: O(n) 每個子問題只會被計算一次，並且儲存在 dp 字典中
    space: O(n)
    - call stack space O(n): 最壞情況下，遞歸深度為 O(n)，即 n 次遞歸呼叫會佔用 O(n) 的堆疊空間。
    - dp dict O(n): dp 字典中儲存了 n+1 個子問題的結果，因此需要 O(n) 的額外空間。
    """
    def helper(nums: List[int]) -> int:
        n = len(nums)
        # 檢查是否已經計算過
        if n in dp:
            return dp[n]
        else:
            # 偷與不偷
            steal = helper(nums[:-2]) + nums[-1]    # 前n-2店家能偷的最佳解 + 第n家店（-1是因爲python的index是從0開始）
            not_steal = helper(nums[:-1])           # 前n-1店家能偷的最佳解
            dp[n] = max(steal, not_steal)
            return dp[n]

    # 建立一個 dict 來儲存已經計算過的子問題 也把最小問題放進去
    dp = {0: 0, 1: nums[0]}
    return helper(nums)

Step3: Iterative + Tabulation

接下來，因為Recursive的缺點是有call stack size的限制，所以我們可以使用Iterative，來避免這個問題

1
2
3
4
5
6
7
8
9
10
11
12
13
def rob3(self, nums: List[int]) -> int:
    """
    time: O(n) 每個子問題只會被計算一次，並且儲存在 dp 字典中
    space: O(n) 只需要一個dp list
    """
    dp = [0, nums[0]]
    if n == 0: return dp[0]
    elif n == 1: return dp[1]
    for i in range(2, len(nums)+1):
        steal = dp[i-2] + nums[i-1] # 偷到前兩個的最佳解 + 偷當前的因為從0開始所以要-1
        not_steal = dp[i-1]         # 只偷到前一個的最佳解
        dp.append(max(steal, not_steal))
    return dp[-1]

Step4: Iterative with Constant Space

最後，我們再思考一下，目前時間複雜度已經到極限了，但是空間複雜度是不是可以再省一點？因為我們只需要前面兩個步驟的結果就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rob4(self, nums: List[int]) -> int:
    """
    time: O(n) 每個子問題只會被計算一次，並且儲存在 dp 字典中
    space: O(1) 只需要constant個變數
    """
    n = len(nums)
    if n == 0: return 0
    elif n == 1: return nums[0]

    prev2, prev1 = 0, nums[0]
    for i in range(2, len(nums)+1):
        best = max(prev2 + nums[i-1], prev1)    # 偷（偷到前兩個+目前） 與 不偷（偷到前一個）
        prev2 = prev1                       # 更新pre變成prev2
        prev1 = best                        # 目前的best是prev1繼續算下一個

    return prev1

3 總結

這題不難，我覺得所有的dp題目最有挑戰性的就是要先知道他的recursive formula，只要能夠實作出來，其他的優化都是小case。