198. 打家劫舍

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0){return 0;}else if(nums.size()==1){return nums[0];}else if(nums.size()==2){return max(nums[0],nums[1]);}vector<int> dp(nums.size()+1,0);dp[0] = nums[0];dp[1] = nums[1];dp[2] = nums[2] +nums[0];for(int i=3;i<nums.size();i++){dp[i] = max(dp[i-2],dp[i-3])+nums[i];}return max(dp[nums.size()-1],dp[nums.size()-2]);}
};

比較基礎，定義以為數組，確定邊界值，每次dp【i】的大小時，前面的元素加上現在位置的值，但是不能相鄰，可以是前面第2個，也可以是第3個，選擇其中大的，最后判斷倒是1，2的最大值。

213. 打家劫舍 II

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if(n == 0) return 0;if(n == 1) return nums[0];if(n == 2) return max(nums[0], nums[1]);// 情況1：偷第一間，不偷最后一間 (0 到 n-2)vector<int> dp1(n, 0);dp1[0] = nums[0];dp1[1] = max(nums[0], nums[1]);for(int i = 2; i < n-1; i++) {dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]);}int result1 = dp1[n-2];// 情況2：不偷第一間，可以偷最后一間 (1 到 n-1)vector<int> dp2(n, 0);dp2[0] = 0;dp2[1] = nums[1];dp2[2] = max(nums[1], nums[2]);for(int i = 3; i < n; i++) {dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i]);}int result2 = dp2[n-1];return max(result1, result2);}
};

🎯 問題分析

環形房屋的特殊性：第一間房和最后一間房相鄰，不能同時偷竊。這打破了線性結構的簡單性。

🔍 核心思路

將環形問題分解為兩個線性問題：

情況1：偷第一間房 → 不能偷最后一間房

• 考慮房屋范圍：[0, n-2]（從第一間到倒數第二間）

• 這樣確保第一間和最后一間不會同時被偷

情況2：不偷第一間房 → 可以偷最后一間房

• 考慮房屋范圍：[1, n-1]（從第二間到最后一間）

• 這樣也確保第一間和最后一間不會同時被偷

🧮 動態規劃過程

對于每個線性子問題，使用標準打家劫舍算法：

狀態定義：dp[i]?表示偷到第i間房時的最大金額

狀態轉移方程：

cpp

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

解釋：

• dp[i-1]：不偷第i間房，保持前i-1間的最大金額

• dp[i-2] + nums[i]：偷第i間房，加上前i-2間的最大金額

📊 具體例子分析

假設?nums = [2, 3, 2, 4]

情況1：偷第一間，不偷最后一間 → [2, 3, 2]

text

dp[0] = 2
dp[1] = max(2, 3) = 3  
dp[2] = max(3, 2+2) = max(3, 4) = 4
結果：4

情況2：不偷第一間，偷最后一間 → [3, 2, 4]

text

dp[0] = 0 (不偷第一間)
dp[1] = 3
dp[2] = max(3, 0+2) = 3
dp[3] = max(3, 3+4) = max(3, 7) = 7  
結果：7

最終結果：max(4, 7) = 7

🎪 為什么這樣分解有效？

因為環形結構中，第一間和最后一間只能二選一：

• 要么選擇偷第一間（就必須放棄最后一間）

• 要么選擇不偷第一間（就可以考慮偷最后一間）

這兩種情況覆蓋了所有可能性，且不會出現第一間和最后一間同時被偷的情況。

337. 打家劫舍 III

class Solution {
public:int rob(TreeNode* root) {auto result = dfs(root);return max(result.first, result.second);}private:// 返回pair: first=不偷當前節點的最大值, second=偷當前節點的最大值pair<int, int> dfs(TreeNode* node) {if (!node) return {0, 0};auto left = dfs(node->left);auto right = dfs(node->right);// 不偷當前節點：左右子節點可以偷或不偷，取最大值int not_rob = max(left.first, left.second) + max(right.first, right.second);// 偷當前節點：左右子節點都不能偷int rob = node->val + left.first + right.first;return {not_rob, rob};}
};

對于二叉樹結構的打家劫舍，需要使用后序遍歷+動態規劃：

每個節點返回一個pair{不偷的最大值, 偷的最大值}：

• dp[0]：不偷當前節點時的最大金額

• dp[1]：偷當前節點時的最大金額

狀態轉移：

• 不偷當前節點：max(左子節點不偷, 左子節點偷) + max(右子節點不偷, 右子節點偷)

• 偷當前節點：當前節點值 + 左子節點不偷 + 右子節點不偷