python 中的房屋強盜

假設有一個城市，城市中的每棟房屋都有一個特定的數量。一個強盜想在一個晚上搶走這筆錢。這座城市有一個安全系統，即如果兩棟相鄰的房屋在同一天被破壞，系統將自動報警。我們必須找到這個強盜能搶到的最大金額？

提供了一個數組，在索引 i 處，A[i] 是第 i 棟房屋中存在的金額。假設陣列如下：A = [2, 7, 10, 3, 1]，則結果為 13。最大金額取自房屋 1（價值 2）、房屋 3（價值 10）、房屋 5（價值 1），因此總金額為 13

為了解決這個問題，我們將遵循此方法 -

  • 取 prev1 := 0 且 prev2 = 0
  • 對於 i = 0 至 A 的長度
    • temp := prev1
    • prev1 := prev2 + A[i] 和 prev1 的最大值
    • prev2 = temp
  • 返回 prev1

示例

我們看看下面的實現來獲得更好的理解 -

 即時演示

class Solution(object):
   def rob(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      prev2 = 0
      prev1 = 0
      for i in range(0,len(nums)):
         temp = prev1
         prev1 = max(prev2+nums[i],prev1)
         prev2 = temp
      return prev1
ob1 = Solution()
print(ob1.rob([2,7,10,3,1]))

輸入

nums = [2,7,10,3,1]

輸出

13

更新於：2020 年 4 月 28 日

1K+ 瀏覽量

開啟你的 職業生涯

完成課程以獲得認證

開始
廣告