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+ 浏览量

开启你的 职业生涯

完成课程以获得认证

开始
广告