파이썬 알고리즘 인터뷰 88. 집도둑

https://leetcode.com/problems/house-robber/description/

 

전체 코드

메모이제이션

class Solution:
    def __init__(self):
        self.dp = collections.defaultdict()

    def rob(self, nums: List[int]) -> int:
        def dfs(nums, idx):
            if idx >= len(nums):
                return 0

            if idx in self.dp:
                return self.dp[idx]

            n1 = dfs(nums, idx + 2)
            n2 = dfs(nums, idx + 3)
            result = nums[idx] + max(n1, n2)
            self.dp[idx] = result
            return self.dp[idx]

        n1 = dfs(nums, 0, 0)
        n2 = dfs(nums, 1, 0)
        return max(n1, n2)

타뷸레이션

class Solution:
    def rob(self, nums: List[int]) -> int:
        if nums is None:
            return 0

        if len(nums) <= 2:
            return max(nums)

        sums = [nums[0], max(nums[0], nums[1])]
        for i in range(2, len(nums)):
            sums.append(max(sums[i - 1], sums[i - 2] + nums[i]))

        return sums[-1]

 

분석

메모이제이션

첫번째로 메모이제이션 방식이 떠올랐다. idx+2, idx+3 양쪽으로 분기하다가 백트래킹시 양쪽의 값 중 더 큰 값을 가져온다. 이후 현재 nums[idx] 값과 더한 후 해당 값을 반환하면 루트노드에서 최대값을 반환하게 된다.

백트래킹 시 현재 인덱스를 키로 반환값에 사용할 num[idx] + max(n1, n2)를 저장하고 다음 재귀 연산 시 해당 인덱스가 있으면 바로 반환하여 가치지기를 진행한다.

0, 1 인덱스에 대해 각각 진행하고 최대값을 반환하면 결과를 구할 수 있다.

타뷸레이션

해설에는 타뷸레이션 방식으로 문제를 풀이하였다. 바로 타뷸레이션으로 풀 수 있겠다는 생각이 들지 않아 내용을 정리해보았다.

다음과 같은 리스트 nums가 있을 때 먼저 0, 1번 인덱스의 값을 sums에 이관한다. 여기서 1번 인덱스는 max(nums[0], nums[1])를 통해 더 큰 값을 저장하도록 한다. i=2부터 순회하도록 한다.

이 후 max(sums[i - 1], sums[i - 2] + nums[i])에 따라 다음과 같이 진행한다. 

만약 max(num[0], nums[1])으로 sums[1]을 초기화하지 않았다면 다음과 같이 16이 출력된다. nums[i] + nums[i+3] = 17이 최대 값이므로 문제가 발생한다. 따라서 sums[1]=max(num[0], nums[1])으로 초기화한다.

다음과 같이 sum[i-1] > sum[i-2] + nums[i]인 경우 sum[i-1]을 그대로 추가한다. 이는 [8, 3, 1]의 합보다 [8, 9]의 합이 더 크기 때문에 이와 같은 처리를 한다.

전체 진행 패턴은 다음과 같다.