LeetCode - House Robber（偷竊）

題目描述

你是一名小偷，計劃打劫一排相鄰的房子。每棟房子內都有一筆金錢，但相鄰的房子有保全系統，若你同時打劫相鄰的房子，會觸發警報。給定一個整數數組 nums，代表每棟房子內的金額，請你計算出你能夠打劫到的最大金額。

範例：

輸入：nums = [1, 2, 3, 1]
輸出：4
解釋：偷竊第 1 和第 3 棟房子（1 + 3 = 4）。

輸入：nums = [2, 7, 9, 3, 1]
輸出：12
解釋：偷竊第 1、第 3 和第 5 棟房子（2 + 9 + 1 = 12）。

限制：

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

解法思路

這道題目可以使用動態規劃來解決。定義一個數組 dp，其中 dp[i] 表示到達第 i 棟房子時能夠打劫到的最大金額。

動態規劃步驟

1. 初始化：
   • 當 i = 0 時，dp[0] = nums[0]，因為只有一棟房子可以打劫。
   • 當 i = 1 時，dp[1] = max(nums[0], nums[1])，因為只能選擇打劫第一棟或第二棟房子。
2. 遞推公式：
   • 對於每一棟房子 i（從 2 開始），可以選擇：
     • 不打劫這棟房子，則最大金額為 dp[i-1]。
     • 打劫這棟房子，則最大金額為 nums[i] + dp[i-2]（因為不能打劫相鄰的房子）。
   • 因此，遞推公式為： [ dp[i] = \max(dp[i-1], nums[i] + dp[i-2]) ]
3. 結果：最終返回 dp[len(nums) - 1]，即打劫到最後一棟房子時的最大金額。

代碼實現

以下是 Python 的實現：

def rob(nums):
    if not nums:
        return 0
    elif len(nums) == 1:
        return nums[0]
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])

    return dp[-1]

代碼解析

1. 邊界條件：處理空數組和只有一棟房子的情況。
2. 初始化 dp 數組：設置 dp[0] 和 dp[1] 的初始值。
3. 更新 dp：從第 2 棟房子開始，計算能打劫到的最大金額。
4. 返回結果：最終返回最後一個元素 dp[-1]。

時間和空間複雜度

• 時間複雜度：O(n)，需要遍歷整個數組。
• 空間複雜度：O(n)，使用了 dp 數組來儲存每一步的結果。

空間優化

可以進一步優化空間複雜度，只用兩個變量來儲存前兩個結果，而不使用完整的 dp 數組：

def rob(nums):
    if not nums:
        return 0
    elif len(nums) == 1:
        return nums[0]

    prev1, prev2 = 0, 0
    
    for num in nums:
        temp = prev1
        prev1 = max(prev1, prev2 + num)
        prev2 = temp

    return prev1

這樣，空間複雜度可以降低到 O(1)。