House Robber

박수빈·2022년 3월 20일
0

leetcode

목록 보기
46/51
post-custom-banner

문제

  • 두 이웃 집이 같은 밤에 도둑질 당하면 신고함
  • 신고 당하지 않고 털 수 있는 최대 금액은?

풀이

  • 연속으로 두 칸을 선택할 수는 없음
  • dp[i] = [max(dp[i-2])+nums[i], dp[i-1][0]]
  • dp[i][0] -> 두 집 전의 max + 이번 집
  • dp[i][1] -> adjecent 집
class Solution:
    def rob(self, 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)

결과

profile
개발자가 되고 싶은 학부생의 꼼지락 기록
post-custom-banner

0개의 댓글