陕西建设网一体化平台,seo推广怎么弄,网站开发与管理学什么,电子商务网站建设试题题目
BM79 打家劫舍(二) 描述 你是一个经验丰富的小偷#xff0c;准备偷沿湖的一排房间#xff0c;每个房间都存有一定的现金#xff0c;为了防止被发现#xff0c;你不能偷相邻的两家#xff0c;即#xff0c;如果偷了第一家#xff0c;就不能再偷第二家#xff0c;如…题目
BM79 打家劫舍(二) 描述 你是一个经验丰富的小偷准备偷沿湖的一排房间每个房间都存有一定的现金为了防止被发现你不能偷相邻的两家即如果偷了第一家就不能再偷第二家如果偷了第二家那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形即第一个房间和最后一个房间视为相邻。 给定一个长度为n的整数数组nums数组中的元素表示每个房间存有的现金数额请你计算在不被发现的前提下最多的偷窃金额。 分析
跟【动态规划-BM78 打家劫舍(一)】的区别是最后一家与第一家相连成环。
这时第一家与最后一定有一个是一定不取的分两种情况讨论。
当取第一家时只需在原有基础上不要遍历到最后一家即可ansdp[n-1] 当不取第一家时dp[1] 0, 遍历到最后一家ans dp[n]
取两种情况的最大值。
代码
class Solution:def rob(self , nums: List[int]) - int:# write code heren len(nums)dp [0]*(n1)# 取第一家dp[1] nums[0]# 最后一家不管不遍历for i in range(2,n):dp[i] max(dp[i-1],dp[i-2]nums[i-1])# 取到最后一家的前一家ans1 dp[n-1]# 不取第一家dp [0]*(n1)# 遍历到最后一家for i in range(2,n1):dp[i] max(dp[i-1],dp[i-2]nums[i-1])# 取到最后一家ans2 dp[n]return max(ans1,ans2)
