[리트코드] 0213. 집도둑 ii

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

당신은 거리의 집을 털려는 전문 강도입니다. 각 집에는 일정 금액의 돈이 숨겨져 있습니다. 원으로 배열되었습니다. 즉, 첫 번째 집은 마지막 집의 이웃이고, 인접한 집에는 보안 시스템이 연결되어 있습니다. 같은 밤에 인접한 두 집에 침입하면 자동으로 경찰에 연락됩니다..

정수 배열이 주어지면 숫자 각 집의 금액을 나타내는 반환 오늘 밤에 훔칠 수 있는 최대 돈 경찰에 알리지도 않고.

예시 1:

입력: 숫자 = [2,3,2]
산출: 3
설명: 집 1(돈 = 2)을 털고 이어서 집 3(돈 = 2)을 털 수는 없습니다. 왜냐하면 두 집이 인접한 집이기 때문입니다.

예 2:

입력: 숫자 = [1,2,3,1]
산출: 4
설명: 1번 집(돈 = 1)을 털고 3번 집(돈 = 3)을 훔칠 수 있습니다. = 1 + 3 = 4.

예시 3:

입력: 숫자 = [1,2,3]
산출: 3

제약:

1 <= 숫자.길이 <= 100
0 <= 숫자[i] <= 1000

파이썬

				
					# 시간 복잡도: O(n) # 공간 복잡도: O(n) 입력 가져오기 목록 클래스 솔루션: def rob(self, nums: List[int]) -> int: def robMoney(nums: List[int], start : int, end: int) -> int: dp = [0] * (end - start) dp[0] = nums[start] dp[1] = max(dp[0], nums[start + 1]) 범위(시작 + 2, 끝)에 있는 i의 경우: dp[i-start] = max(nums[i] + dp[i-start - 2], dp[i-start - 1]) return dp[-1] n = len(nums) n == 0인 경우: 0을 반환합니다. n == 1인 경우 nums[0]을 반환합니다. n == 2인 경우: max(nums[0], nums[1])를 반환합니다. Money1 = robMoney(nums, 0, n - 1) 돈2 = robMoney(nums, 1, n) return max(money1, 돈2) nums = [2, 3, 2] print(Solution().rob(nums)) nums = [1, 2, 3, 1] print(Solution().rob(nums)) nums = [1, 2, 3] print(Solution().rob(nums))

중간

파이썬

관련 기사