利用动态规划解leetcode第213题：打家劫舍||
最新回答
幼儿园的小酷比
2026-05-16 05:00:01
解题思路：
本题是LeetCode第198题“打家劫舍”的进阶版，房屋排列方式由直线变为圆圈，即第一个房屋和最后一个房屋相邻。由于相邻房屋不能同时被偷窃，因此我们需要分别考虑两种情况：
- 偷窃第一间房屋：此时不能偷窃最后一间房屋，因此问题转化为对房屋区间[0, n-2]进行偷窃。
- 不偷窃第一间房屋：此时可以偷窃最后一间房屋，问题转化为对房屋区间[1, n-1]进行偷窃。
最终结果为这两种情况的最大值。
代码实现：
class Solution {public: int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; // 分两种情况讨论 vector<int> nums1(nums.begin(), nums.end() - 1); // [0, n-2] vector<int> nums2(nums.begin() + 1, nums.end()); // [1, n-1] return max(rob1(nums1), rob1(nums2)); } // 198题的动态规划解法 int rob1(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; int dp[n + 1]; dp[0] = 0; // 不偷窃任何房屋 dp[1] = nums[0]; // 只偷窃第一间房屋 for (int i = 2; i <= n; ++i) { dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]); } return dp[n]; }};代码解释：
rob函数：
处理边界情况：当房屋数量为0时返回0，为1时返回唯一房屋的金额。
将问题分解为两个子问题：偷窃[0, n-2]区间和不偷窃第一间房屋的[1, n-1]区间。
调用rob1函数分别求解两个子问题，并返回最大值。
rob1函数：
使用动态规划求解直线排列房屋的偷窃问题。
初始化dp数组，其中dp[i]表示偷窃前i间房屋的最大金额。
递推关系：dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])，即当前房屋的最大金额为偷窃当前房屋与前两间房屋的最大金额之和，或不偷窃当前房屋而取前一间房屋的最大金额。
示例验证：
示例1：
输入：[2,3,2]
分解为[2,3]和[3,2]两个子问题。
[2,3]的最大金额为3，[3,2]的最大金额为3。
返回max(3, 3) = 3。
示例2：
输入：[1,2,3,1]
分解为[1,2,3]和[2,3,1]两个子问题。
[1,2,3]的最大金额为4，[2,3,1]的最大金额为3。
返回max(4, 3) = 4。
复杂度分析：
- 时间复杂度：O(n)，其中n为房屋数量。每个子问题需要遍历一次数组。
- 空间复杂度：O(n)，用于存储dp数组。可通过滚动数组优化至O(1)。
优化空间复杂度：
int rob1(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; int prev2 = 0, prev1 = nums[0]; for (int i = 1; i < n; ++i) { int current = max(prev2 + nums[i], prev1); prev2 = prev1; prev1 = current; } return prev1;}通过使用两个变量prev2和prev1替代dp数组，空间复杂度优化至O(1)。
热门标签
