济南做网站企业,wordpress weiaid,代理网址浏览器,周口建设企业网站公司【LetMeFly】213.打家劫舍 II#xff1a;动动态规划
力扣题目链接#xff1a;https://leetcode.cn/problems/house-robber-ii/
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 #xff0c;这意味…【LetMeFly】213.打家劫舍 II动动态规划
力扣题目链接https://leetcode.cn/problems/house-robber-ii/
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 示例 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 [1,2,3]
输出3提示
1 nums.length 1000 nums[i] 1000
方法一动态规划
假设不考虑“环形”那么我们应该怎么做
很简单遍历数组使用两个变量lastRob和lastNot分别代表上次是否打劫了。
如果上次打劫了那么这次就不能打劫 t h i s N o t max ( l a s t R o b , l a s t N o t ) thisNot \max(lastRob, lastNot) thisNotmax(lastRob,lastNot)如果上次没打劫那么这次就打劫 t h i s R o b l a s t N o t n u m s [ i ] thisRob lastNot nums[i] thisRoblastNotnums[i]
然后更新lastRob和lastNot为thisRob和thisNot。
最终返回lastRob和lastNot的最大值即为答案。
加上环形这一限制应怎么处理
很简单环形的唯一限制就是打劫第一家的话不能打劫最后一家打劫最后一家的话不能打劫第一家。
因此在 [ 0 , l e n ( n u m s ) − 1 ] [0, len(nums) - 1] [0,len(nums)−1]和 [ 1 , l e n ( n u m s ) ] [1, len(nums)] [1,len(nums)]中分别求一次取最大即可。
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
private:int realRob(vectorint nums, int l, int r) {int lastRob nums[l], lastNot 0;for (int i l 1; i r; i) {int newRob lastNot nums[i], newNot max(lastRob, lastNot);lastRob newRob, lastNot newNot;}return max(lastRob, lastNot);}
public:int rob(vectorint nums) {if (nums.size() 1) {return nums[0];}return max(realRob(nums, 0, nums.size() - 1), realRob(nums, 1, nums.size()));}
};Python
# from typing import Listclass Solution:def realRob(self, nums: List[int], l: int, r: int) - int:lastRob, lastNot nums[l], 0for i in range(l 1, r):lastRob, lastNot lastNot nums[i], max(lastNot, lastRob)return max(lastRob, lastNot)def rob(self, nums: List[int]) - int:if len(nums) 1:return nums[0]return max(self.realRob(nums, 0, len(nums) - 1), self.realRob(nums, 1, len(nums)))同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132945449
