리트코드 198번 Houser Robber (python)

Problem

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

Solution

내 풀이

from collections import defaultdict
from typing import List

class Solution:
    money = defaultdict(int)

    def rob(self, nums: List[int]) -> int:
        def get_money(idx):
            if idx < 0:
                return 0
            elif idx < 2:
                return nums[idx]

            if self.money[idx]:
                return self.money[idx]
            self.money[idx] = get_money(idx - 2) + get_money(idx - 3) + nums[n]
            return self.money[idx]

        for n in range(len(nums)):
            self.money[n] = max(get_money(n - 2), get_money(n - 3)) + nums[n]
            print(self.money, get_money(n - 2), get_money(n - 3), nums[n])

        return max(self.money.values())

n 번째 집을 훔치는 경우 최대 값은 n-2번째 훔치고 오는 경우와 n-1번째 훔치는 경우 중 더 큰 값 + n번째에서 얻을 수 있는 돈의 합이다.

해당 접근법으로 문제를 풀었으나 파이참에서는 괜찮은데 리트코드에서는 nums=[0]인 경우에 12가 나온다. 원인을 잘 모르겠다..

다른 풀이

from collections import defaultdict
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)

        dp = {}
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        return dp.popitem()[1]

내가 푼 방식에서는 약간 다르게

“i번 집까지 훔쳤을 때 최대 값은 i-1번째의 값과 i-2의 값 + i번째 집에서 얻은 수익 중 더 큰 값이다.” 라는 접근법으로 해결한 풀이이다.

Reference

파이썬 알고리즘 인터뷰 88번