IT评测·应用市场-qidao123.com

标题: 【动态规划-BM79 打家劫舍(二)】 [打印本页]
作者: 东湖之滨    时间: 2024-6-14 20:58
标题: 【动态规划-BM79 打家劫舍(二)】
题目

BM79 打家劫舍(二)
描述
你是一个履历丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，假如偷了第一家，就不能再偷第二家，假如偷了第二家，那么就不能偷第一家和第三家。沿湖的房间构成一个闭合的圆形，即第一个房间和末了一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

分析

跟【动态规划-BM78 打家劫舍(一)】的区别是末了一家与第一家相连成环。
这时，第一家与末了一定有一个是一定不取的，分两种情况讨论。
当取第一家时，只需在原有底子上，不要遍历到末了一家即可，ans=dp[n-1]
当不取第一家时，dp[1] = 0, 遍历到末了一家，ans = dp[n]
取两种情况的最大值。
代码

  1. class Solution:
  2.     def rob(self , nums: List[int]) -> int:
  3.         # write code here
  4.         n = len(nums)
  5.         dp = [0]*(n+1)
  6.         # 取第一家
  7.         dp[1] = nums[0]
  8.         # 最后一家不管，不遍历
  9.         for i in range(2,n):
  10.             dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
  11.         # 取到最后一家的前一家
  12.         ans1 = dp[n-1]
  13.         # 不取第一家
  14.         dp = [0]*(n+1)
  15.         # 遍历到最后一家
  16.         for i in range(2,n+1):
  17.             dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
  18.         # 取到最后一家
  19.         ans2 = dp[n]
  20.         return max(ans1,ans2)
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4