Python中的强盗
假设有一个城市,并且城市中的每个房屋都有一定数量。一个抢劫犯想在一晚之内抢钱。该城市拥有一个安全系统,就好像同一天晚上连续破坏了两栋房屋一样,它将自动报警。因此,我们必须找出强盗可以劫持的最大金额?
提供了一个数组,在索引i处,A[i]是第i个房屋中存在的数量。假设数组是这样的:A=[2,7,10,3,1],则结果将为13。最大值取自house1(值2),house3(值10)和house5(值1)。),因此总数为13
为了解决这个问题,我们将遵循这种方法-
取prev1:=0和prev2=0
对于i=0到A的长度-
temp:=prev1
prev1:=prev2+A[i]和prev1的最大值
prev2=临时
返回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