[LeetCode] House Robber

첫 번째 풀이

class Solution:
    from collections import defaultdict
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
            
        dp = defaultdict(int)
        
        dp[len(nums)-1] = nums[-1]
        dp[len(nums)-2] = nums[-2]

        for i in range(len(nums)-3, -1, -1):
            dp[i] = nums[i] + max([dp[k] for k in dp if k >= i + 2])
            # print(dp[i])
            
        return max(list(dp.values()))

오 주여.. 처음 풀 때 못 풀겠어서 몇 주간 방치하다가 맑아진 머리로 푸니 금방 풀렸다.
컨디션이 참 중요한 것 같다.

DP로 뒤에 집부터 해당 집 이후로 털었을 때 최대 이득을 defaultdict에 저장해놓고,
앞으로 가면서 뒤에 갈 수 있는 집의 각 최대값들을 key로 불러와서 그 중 제일 큰 값을 더해주면서 딕셔너리를 채웠다.

dictionary
key: 집 위치 인덱스, value: 해당 위치에서 털 수 있는 최대 이득