題目連結: 213. House Robber II

題目描述:與前天的題目幾乎一樣，但增加了一個條件：所有房屋圍成一個環。這意味著第一間房子和最後一間房子是相鄰的。同樣地，你不能偷竊相鄰的房屋。請問你能偷竊到的最高總金額是多少？

Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:
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 3:
Input: nums = [1,2,3]
Output: 3

Python

解題思路:
昨天的解法沒有考慮到「頭尾相連」的約束。如果我們直接套用，可能會同時選擇偷第一間和最後一間，這在環形結構中是不被允許的。
不產生環形的方法只要把問題劃分不偷第一間與偷第一間，那麼解決問題不就與昨天一模一樣了嗎!

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob1(nums):
            dp0 = 0
            dp1 = 0
            for i in range(len(nums)):
                curr =max(dp1,dp0+nums[i])
                temp = dp1
                dp1 = curr 
                dp0 = temp
            return dp1
        if len(nums)<=3:
            return max(nums)
        sum1 = rob1(nums[1:])# 第一間不偷
        sum2 = rob1(nums[:-1])# 最後一間偷
        return max(sum1,sum2)

演算法分析:

• 這個問題比「House Robber」只多了一個「環形」的約束，即第一間房 nums[0] 和最後一間房 nums[n-1] 是相鄰的。
• 不過先考慮如果nums陣列數量<=3時，直接回傳最大值就行了。

複雜度分析:

• 時間複雜度為 O(n)(演算法的核心是一個 for 迴圈，它遍歷了 nums 陣列一次。)。
  1. 第一次呼叫 rob_linear(nums[1:])，傳入的子陣列長度也為 n-1。其時間複雜度為 O(n-1)。
  2. 第二次呼叫 rob_linear(nums[:-1])，傳入的子陣列長度也為 n-1。時間複雜度同樣是 O(n-1)。
  3. 總的時間複雜度是 O(n-1) + O(n-1)忽略常數和低階項，所以最終時間複雜度為 O(n)。
• 空間複雜度： O(1) 或 O(n)(這個演算法的核心邏輯只需要 O(1) 的輔助空間。，為了程式碼的簡潔，使用了切片操作，這會產生 O(n) 的臨時空間)。

有問題可以底下留言!
下回見!!