📘 題目敘述
你是一個專業小偷，計畫沿著一條街偷房子。每間房子有一筆金額，並且有一個用顏色代碼表示的保全系統。
給你兩個長度為 n 的整數陣列 nums 和 colors，其中 nums[i] 是第 i 間房子的金額，colors[i] 是第 i 間房子的顏色代碼。
如果兩間相鄰房子的顏色代碼相同，你不能同時偷這兩間相鄰房子。
請回傳你能偷到的最大金額。
條件限制
1 <= n == nums.length == colors.length <= 10^51 <= nums[i], colors[i] <= 10^5
🧠 解題思路
這題看起來像經典 House Robber，但限制被改成：
- 只有在「相鄰且顏色相同」時才不能兩間都偷
- 如果相鄰但顏色不同，是可以連偷的
所以我用 DP 做「走到第 i 間」的最佳金額，並且用兩個狀態分開記：
ymoney[i]：走到第 i 間時，「第 i 間有偷」的最大金額nmoney[i]：走到第 i 間時，「第 i 間沒偷」的最大金額
這樣我在處理第 i 間要不要偷時，只要看：
- 如果第 i 間不偷，那就沿用前一間偷/不偷的最大值
- 如果第 i 間要偷：
- 若
colors[i] == colors[i-1]，代表相鄰同色，不能跟i-1同時偷，所以只能接在「i-1沒偷」的狀態上 - 若
colors[i] != colors[i-1]，代表相鄰不同色，可以接在走到i-1的最佳結果（偷或不偷都行）
- 若
這個想法的重點是：限制只跟「前一間有沒有偷」以及「顏色是否相同」有關，所以兩狀態 DP 就能完整描述。
所有變數
n：房子數量ymoney：ymoney[i]代表到第i間為止，且第i間有偷的最大金額nmoney：nmoney[i]代表到第i間為止，且第i間沒偷的最大金額
🪜 主要流程步驟
1. 先定義兩個 DP 狀態，分別代表「偷 i」與「不偷 i」
我用 ymoney / nmoney 把「第 i 間是否偷」這件事拆成兩條路，因為限制只跟相鄰有關，這樣最清楚也最好轉移。
2. 初始化第 0 間房子
第 0 間只有兩種狀態：
- 偷第 0 間：
ymoney[0] = nums[0] - 不偷第 0 間：
nmoney[0] = 0
3. 先更新「第 i 間不偷」的狀態 nmoney[i]
如果第 i 間不偷，那走到 i 的最佳結果就是走到 i-1 的最大值：
nmoney[i] = max(ymoney[i - 1], nmoney[i - 1])
意思是：不管 i-1 偷不偷，我都可以選一個比較大的結果，然後第 i 間保持不偷。
4. 再更新「第 i 間要偷」的狀態 ymoney[i]，看顏色是否相同決定能不能接前一間偷的狀態
如果我要偷第 i 間，就一定要把 nums[i] 加進來，但能接哪個狀態要看顏色。
當 colors[i] == colors[i - 1]：相鄰同色不能連偷，所以第 i 間只能接在「i-1 沒偷」的狀態上：
ymoney[i] = nums[i] + nmoney[i - 1]
當 colors[i] != colors[i - 1]：相鄰不同色可以連偷，所以第 i 間可以接在走到 i-1 的最佳結果上，也就是 nmoney[i]：
ymoney[i] = nums[i] + nmoney[i]
因為 nmoney[i] 已經是 max(ymoney[i-1], nmoney[i-1])，代表走到 i-1 的最佳值。
5. 最後答案是「最後一間偷或不偷」兩者最大值
走到最後一間 n-1，答案就是：
max(ymoney[n - 1], nmoney[n - 1])
⏱️ 複雜度
- 時間複雜度：
O(n)
只掃一次陣列，每間房子更新常數次。 - 空間複雜度：
O(n)
使用兩個長度為n的 DP 陣列。
如果要再省空間，其實可以只留上一格的 ymoney / nmoney 變成 O(1)，但你這份寫法是最直觀、最好閱讀的版本。
💻 程式碼實作
class Solution {
public:
long long rob(vector<int>& nums, vector<int>& colors) {
int n = nums.size();
vector<long long> ymoney(n); // i有偷的最佳
vector<long long> nmoney(n); // i沒偷的最佳
ymoney[0] = nums[0];
nmoney[0] = 0;
for (int i = 1; i < n; i++) {
nmoney[i] = max(ymoney[i - 1], nmoney[i - 1]);
if (colors[i] == colors[i - 1]) {
ymoney[i] = nums[i] + nmoney[i - 1];
} else {
ymoney[i] = nums[i] + nmoney[i];
}
}
return max(ymoney[n - 1], nmoney[n - 1]);
}
};
🔗 題目連結
https://leetcode.com/contest/biweekly-contest-176/problems/house-robber-v/