House Robber 2
문제
- house robber와 같은 문제
- 대신 마지막 집과 첫 집이 이웃이다
풀이
- 1번집으로 시작해서 n-1번 집으로 끝나는 경우
- 0번집으로 시작해서 n-2번 집으로 끝나는 경우
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)>1:
fromFirst = robbing(nums[:-1])
toLast = robbing(nums[1:])
return max(fromFirst, toLast)
return nums[0]
def robbing(nums: List[int]) -> int:
N = len(nums)
if N > 1:
dp = [[0,0] for _ in range(N)]
dp[0][0] = nums[0]
dp[1][1] = nums[0]
dp[1][0] = nums[1]
for i in range(2, N):
dp[i][0] = max(dp[i-2]) + nums[i]
dp[i][1] = dp[i-1][0]
return max(dp[-1])
else:
return max(nums)
결과
- 1번집으로 시작해서 n-1번 집으로 끝나는 경우
- 0번집으로 시작해서 n-2번 집으로 끝나는 경우
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)>1:
fromFirst = robbing(nums[:-1])
toLast = robbing(nums[1:])
return max(fromFirst, toLast)
return nums[0]
def robbing(nums: List[int]) -> int:
N = len(nums)
if N > 1:
dp = [[0,0] for _ in range(N)]
dp[0][0] = nums[0]
dp[1][1] = nums[0]
dp[1][0] = nums[1]
for i in range(2, N):
dp[i][0] = max(dp[i-2]) + nums[i]
dp[i][1] = dp[i-1][0]
return max(dp[-1])
else:
return max(nums)
결과
Author And Source
이 문제에 관하여(House Robber 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/House-Robber-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)