도시가 있고 도시의 각 집에 일정 금액이 있다고 가정합니다. 한 강도가 하룻밤 사이에 돈을 강탈하려고 합니다. 이 도시에는 하나의 보안 시스템이 있습니다. 마치 같은 밤에 두 집이 연속으로 파손된 것처럼 자동으로 경찰에 전화를 겁니다. 그래서 강도가 최대로 강도할 수 있는 금액을 찾아야 합니다.
하나의 배열이 제공되며 인덱스 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 =임시
- 이전1 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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 =임시 반환 prev1ob1 =Solution()print(ob1.rob([2,7,10,3,1]))입력
숫자 =[2,7,10,3,1]출력
13