【leetcode刷题】T162-打家劫舍 II
【题目】
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
【思路】
这道题和【T161-打家劫舍】不同的地方在于，屋围成了一圈。也就是说，第一家和最后一家只能偷窃一家。
那就可以分为两种情况：
1）偷窃第一家，绝对不能偷窃最后一家。dp[i] = max(dp[i-1], dp[i-2]+nums[i])，其中dp[0] = nums[0]， dp[1] = max(nums[0], nums[1])， i=2, 3, …, n-1
2）不偷窃第一家，可以偷窃最后一家。dp[i] = max(dp[i-1], dp[i-2]+nums[i])，其中dp[0] = 0， dp[1] = nums[1]， i=2, 3, …, n
【代码】
python版本
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
if len(nums) < 2:
return max(nums[0], nums[-1])
# 偷窃第0家
a, b = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)-1):
a, b = b, max(b, a+nums[i])
max_money = b
# 不偷窃第0家
a, b = 0, nums[1]
for i in range(2, len(nums)):
a, b = b, max(b, a+nums[i])
return max(max_money, b)
C++版本
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0)
return 0;
if(nums.size() < 2)
return max(nums.front(), nums.back());
// 偷窃第0家
int a = nums[0], b = max(nums[0], nums[1]);
int tmp = 0;
for(int i=2; i < nums.size() - 1; i++){
tmp = b;
b = max(b, a + nums[i]);
a = tmp;
}
int max_money = b;
// 不偷窃第0家
a = 0, b = nums[1];
for(int i=2; i < nums.size(); i++){
tmp = b;
b = max(b, a + nums[i]);
a = tmp;
}
return max(max_money, b);
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-09-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读