題目描述:房屋排列成環形,第一間和最後一間相鄰,不能搶相鄰房屋,求最大金額。
解題思路:由於成環,第一間和最後一間不能同時被搶。解法:將問題拆成兩個子問題:(1)搶 nums[0..n-2](排除最後一間);(2)搶 nums[1..n-1](排除第一間)。分別套用 House Robber I 的解法,取兩者最大值即為答案。
時間複雜度:O(n) — 兩次線性掃描。
空間複雜度:O(1) — 每次只用兩個變數。
1. If n == 1: return nums[0] 2. Define robRange(lo, hi) = House Robber I on nums[lo..hi] 3. Return max(robRange(0, n-2), robRange(1, n-1))
分開處理環 O(n):分別處理不含首或不含尾的情況,取最大值 — 此為本方法。
強行 O(n²):嘗試不同跳過策略,對各策略跑 DP — 時間複雜度更差。