Description
所有房屋排成一個圓圈（第一間和最後一間相鄰）。相鄰房屋不能同時被搶。給定代表每間房屋金額的整數陣列
nums，求能搶到的最大金額。
Example:
Input: nums = [2,3,2] Output: 3
Intuition#
環形問題拆成兩個線性問題：搶第一間就不搶最後一間，反之亦然，取兩者最大值。
- 因為首尾相鄰，不可能同時搶第一間和最後一間
- 分成兩個子問題：
nums[0..n-2]和nums[1..n-1] - 每個子問題就是 House Robber I
Approaches#
- Two-Pass Memoization (Top-Down) — O(n) / O(n)
- 概念: 對兩個子區間
[0, n-2]和[1, n-1]各跑一次帶 memo 的遞迴 - 時間複雜度:
O(n)- 每個狀態只算一次 - 空間複雜度:
O(n)- memo 陣列 + 遞迴堆疊
class Solution {
fun rob(nums: IntArray): Int {
if (nums.size == 1) return nums[0]
fun robRange(lo: Int, hi: Int): Int {
val memo = IntArray(nums.size) { -1 }
fun dp(i: Int): Int {
if (i > hi) return 0
if (memo[i] != -1) return memo[i]
memo[i] = maxOf(nums[i] + dp(i + 2), dp(i + 1))
return memo[i]
}
return dp(lo)
}
return maxOf(robRange(0, nums.size - 2), robRange(1, nums.size - 1))
}
}- Two-Pass DP Array — O(n) / O(n)
- 概念: 對兩個子陣列各跑一次 House Robber I 的 DP
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun rob(nums: IntArray): Int {
if (nums.size == 1) return nums[0]
fun robRange(start: Int, end: Int): Int {
val dp = IntArray(nums.size)
dp[start] = nums[start]
dp[start + 1] = maxOf(nums[start], nums[start + 1])
for (i in start + 2..end) {
dp[i] = maxOf(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[end]
}
return maxOf(robRange(0, nums.size - 2), robRange(1, nums.size - 1))
}
}⭐ 3. Two-Pass Rolling Variables — O(n) / O(1)
- 概念: 同上但用滾動變數，每次只追蹤前兩個狀態
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun rob(nums: IntArray): Int {
if (nums.size == 1) return nums[0]
fun robRange(start: Int, end: Int): Int {
var prev2 = 0
var prev1 = 0
for (i in start..end) {
val cur = maxOf(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = cur
}
return prev1
}
return maxOf(robRange(0, nums.size - 2), robRange(1, nums.size - 1))
}
}🔑 Takeaways#
- Pattern: 環形 DP — 把環形拆成兩個線性子問題，分別求解再取最大值
- 關鍵技巧: 環形約束的處理套路：首尾互斥，分兩種情況討論