Description
一排房屋各有不同金額，相鄰的房屋不能同時被搶。給定代表每間房屋金額的整數陣列
nums，求在不觸發警報的情況下能搶到的最大金額。
Example:
Input: nums = [2,7,9,3,1] Output: 12
Intuition#
每間房屋只有兩種選擇：搶或不搶。搶了就跳過下一間，不搶則繼續。
- 對於第
i間房屋：搶 →dp[i-2] + nums[i]，不搶 →dp[i-1] - 狀態轉移：
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - 經典的「取或不取」DP 模式
Approaches#
- Memoization (Top-Down DP) — O(n) / O(n)
- 概念: 從第 0 間房屋開始遞迴，每間房屋兩種選擇：搶（跳到
i+2）或不搶（跳到i+1），用 memo 快取重複子問題 - 時間複雜度:
O(n)- 每個狀態只算一次 - 空間複雜度:
O(n)- memo 陣列 + 遞迴堆疊
class Solution {
fun rob(nums: IntArray): Int {
val memo = IntArray(nums.size) { -1 }
return dp(nums, 0, memo)
}
private fun dp(nums: IntArray, i: Int, memo: IntArray): Int {
if (i >= nums.size) return 0
if (memo[i] != -1) return memo[i]
memo[i] = maxOf(nums[i] + dp(nums, i + 2, memo), dp(nums, i + 1, memo))
return memo[i]
}
}- Bottom-Up DP Array — O(n) / O(n)
- 概念: 建立 DP 陣列紀錄到每間房屋為止的最大收益
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun rob(nums: IntArray): Int {
if (nums.size == 1) return nums[0]
val dp = IntArray(nums.size)
dp[0] = nums[0]
dp[1] = maxOf(nums[0], nums[1])
for (i in 2 until nums.size) {
dp[i] = maxOf(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[nums.size - 1]
}
}⭐ 3. Rolling Variables — O(n) / O(1)
- 概念: 只需要前兩個狀態，用兩個變數即可
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun rob(nums: IntArray): Int {
var prev2 = 0
var prev1 = 0
for (num in nums) {
val cur = maxOf(prev1, prev2 + num)
prev2 = prev1
prev1 = cur
}
return prev1
}
}🔑 Takeaways#
- Pattern: 取或不取 (Take or Skip) — 每個元素有兩種決策，取了就跳過相鄰元素
- 關鍵技巧:
prev2代表「不包含前一個」的最大值，prev1代表「包含或不包含前一個」的最大值