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{不偷的最大值, 偷的最大值}：