[leetcode 2024/02/27] 198. House Robber

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

House Robber - LeetCode

 

1. 접근 방법

이번 문제는 memoization을 이용하는 문제이다.

처음에 memoization을 이용하지 않고 구상하였다가, 시간 초과가 났었다..ㅜ

 

특정 index에 도달 했을 때, 다음 값들에서 얻을 수 있는 최댓값이 고정되어 있다. 

따라서, DFS를 구성하되, 특정 index에서 이미 구한 최댓값의 경우, dictionary에 저장해두어, 반복적인 계산을 하지 않아도 되도록 하였다.

 

만약, 도달한 index가 nums list의 범위를 초과하게 되면 0 을 반환해주었다.

 

self.memoization[index] 의 값이 초기값 -1이 아닌 다른 값이 들어 있다면, 이미 해당 index에 대해서 최댓값 계산이 끝난 것이기 때문에, 바로 self.memoization[index] 에 저장되어 있는 값을 반환해 주었다. 

 

만약 저장되어 있지 않은, 처음 접근한 index하면, 우선 해당 Index 값을 더해주고, max(DFS(index + 2), DFS(index + 3))을 통해서 max값을 찾아주었다.

이후, 찾은 값은 dictionary에 넣어주어, 추후에 해당 index에 접근하게 되면 똑같은 계산을 할 필요 없이 바로 값을 return 하도록 해주었다.

 

2. 코드

class Solution:
    def rob(self, nums: List[int]) -> int:
        self.memoization = {i: -1 for i in range(len(nums))}

        def DFS(index):
            if index >= len(nums):
                return 0

            if self.memoization[index] != -1:
                return self.memoization[index]

            rob_current = nums[index] + max(DFS(index + 2), DFS(index + 3))
            self.memoization[index] = rob_current

            return rob_current

        self.max_money = max(DFS(0), DFS(1))
        return self.max_money