[LeetCode] Python - 198. House Robber

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

House Robber - LeetCode

생각

도둑이 i번째 집을 터는경우, i번째 집을 털지 않는 경우로 이 두가지 경우로 나뉘어집니다. 일반화시키면, i번째와 그 이후의 원소들에 대한 부분 문제로 이루어져있습니다. 그렇기 때문에, Top-Down 방식으로 접근하여 DFS와 메모이제이션을 활용하여 풀었습니다.

 

1. base case는 인덱스가 0 보다 작을때이고, 이때는 0을 리턴시켜줍니다.

2. memo[i]가 이미 계산되어 있다면 memo[i] 값을 바로 리턴해줍니다.

3. memo[i]가 계산되어 있지 않다면, i번째 집을 터는 경우(i-2번째 집에 대한 재귀를 호출해야 함.), i번째 집을 털지 않는 경우(i-1번째 집에 대한 재귀 호출해야 함) 중 큰 값을 계산합니다. -> max(dfs(i-2)+nums[i], dfs(i-1)) 이 중 최대값이 memo[i] 에 적어두고 이 값을 리턴시켜줍니다.

4. Top-Down 방식이기 때문에, 마지막 집 인덱스부터 dfs를 호출하여 답을 찾습니다.

 

Python Code

class Solution:
    # 한개랑, 나머지 부분 문제
    # 처음집훔치는경우, 처음집안훔치는경우
    def rob(self, nums: List[int]) -> int:
        
        memo = [-1]*len(nums)
        
        def dfs(i):
            nonlocal memo, nums
            
            if i < 0:
                return 0
            
            if memo[i] >= 0:
                return memo[i]
            
            ret = max(dfs(i-2)+nums[i], dfs(i-1))
            memo[i] = ret
            return ret

        return dfs(len(nums)-1)