【动态规划-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企服之家，中国第一个企服评测及商务社交产业平台。