欢迎访问LeetCode题解合集
题目描述
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,能够偷窃到的最高金额。
示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [0]
输出:0
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
题解:
动态规划。
参考 打家劫舍 一题,这题是一个环,环的话,唯一特殊的地方就是第一个和最后一个房间,于是我们可以分两步:
- 选择第一个房间,那最后一个房间肯定不能偷
- 不选择第一个房间,剩下的部分和 打家劫舍 一毛一样
设 f[i][0/1]
表示考虑前 i
个房间,第 i
个房间偷和不偷对应的最高金额,那么:
f[i][0] = max{f[i - 1][0], f[i - 1][1]}
f[i][1] = f[i - 1][0] + nums[i]
最后的结果就是两步走中的最大值。
注意:选择第一个房间的话,枚举只需要枚举到 n - 2
就行。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if ( !n ) return 0;
if ( n == 1 ) return nums[0];
vector<int> f1(n);
vector<int> f2(n);
f1[0] = nums[0];
for ( int i = 1; i < n - 1; ++i ) {
f1[i] = f2[i - 1] + nums[i];
f2[i] = max( f1[i - 1], f2[i - 1] );
}
int ret = max( f1[n - 2], f2[n - 2] );
f1[0] = 0;
for ( int i = 1; i < n; ++i ) {
f1[i] = f2[i - 1] + nums[i];
f2[i] = max( f1[i - 1], f2[i - 1] );
}
ret = max( {ret, f1[n - 1], f2[n - 1] } );
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:7.6MB,击败:71.86%
*/
使用滚动数组优化:
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if ( !n ) return 0;
if ( n == 1 ) return nums[0];
int f1, f2 = 0, pre_f1;
f1 = nums[0];
for ( int i = 1; i < n - 1; ++i ) {
pre_f1 = f1;
f1 = f2 + nums[i];
f2= max( pre_f1, f2 );
}
int ret = max( f1, f2);
f1 = 0, f2 = 0;
for ( int i = 1; i < n; ++i ) {
pre_f1 = f1;
f1 = f2 + nums[i];
f2= max( pre_f1, f2 );
}
ret = max( {ret, f1, f2 } );
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:7.5MB,击败:88.72%
*/