描述

在上次打劫完一條街道之后，竊賊又發現了一個新的可以打劫的地方，但這次所有的房子圍成了一個圈，這就意味著第一間房子和最后一間房子是挨著的。每個房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯系的防盜系統，且 當相鄰的兩個房子同一天被打劫時，該系統會自動報警。

給定一個非負整數列表，表示每個房子中存放的錢， 算一算，如果今晚去打劫，在不觸動報警裝置的情況下, 你最多可以得到多少錢 。

這題是House Robber的擴展，只不過是由直線變成了圈

您在真實的面試中是否遇到過這個題？
樣例
樣例1

輸入: nums = [3,6,4]
輸出: 6
樣例2

輸入: nums = [2,3,2,3]
輸出: 6

思路：

動態規劃求解
（1）不考慮第一間房子和最后一間房子是挨著的時
考慮前i項的結果dp[i]時，

dp[i]為到達第i個房間時，得到的最大收益，A為房間錢數組。

當i = 1， 返回dp[0] = A[0]

當i = 2， 返回dp[1] = max(A[0], A[1])

當i = 3， 分為偷3號房屋和不偷3號房屋，

偷的情況下， 2號房間就不能偷了，結果為A[2] + dp[0]

不偷的情況下，結果為dp[1]

所以返回dp[2] = max(dp[0] + A[2], dp[1])

以此類推，dp[i] = max(dp[i-2] + A[i], dp[i-1])
（2）考慮第一間房子和最后一間房子是挨著時

區別在于1號房屋和最后一號房屋只能二選一
即把1號房間舍棄，或者最后一號房間舍棄。在這兩種情況下選最優。

class Solution:"""@param nums: An array of non-negative integers.@return: The maximum amount of money you can rob tonight"""def houseRobber(self, nums):# write your code hereif len(nums) == 1:return nums[0]return max(self.houseRobber2(nums[1:]), self.houseRobber2(nums[:-1]))def houseRobber2(self, nums):if len(nums) == 0:return 0dp = [0 for _ in nums]dp[0] = nums[0]for i in range(1, len(nums)):if i == 1:dp[i] = max(nums[0], nums[i])else:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])return dp[-1]c=Solution() d=c.houseRobber([2,3,2,3]) print(d)

結果：6

總結

以上是生活随笔為你收集整理的Leetcode 534打劫房屋II python的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。