213. House Robber II
MediumDescription
所有房屋排成一個圓圈（第一間和最後一間相鄰）。相鄰房屋不能同時被搶。給定代表每間房屋金額的整數陣列
nums，求能搶到的最大金額。
Example:
Input: nums = [2,3,2] Output: 3
Intuition#
環形問題拆成兩個線性問題：搶第一間就不搶最後一間，反之亦然，取兩者最大值。
- 因為首尾相鄰，不可能同時搶第一間和最後一間
- 分成兩個子問題：
nums[0..n-2]和nums[1..n-1] - 每個子問題就是 House Robber I
Approaches#
1: Two-Pass DP Array#
- 概念: 對兩個子陣列各跑一次 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))
}
}⭐2: Two-Pass Rolling Variables#
- 概念: 同上但用滾動變數，每次只追蹤前兩個狀態
- 時間複雜度:
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 — 把環形拆成兩個線性子問題，分別求解再取最大值
- 關鍵技巧: 環形約束的處理套路：首尾互斥，分兩種情況討論