LeetCode 198. House Robber

파이썬 알고리즘 인터뷰 88번(리트코드 198번) House Robber
https://leetcode.com/problems/house-robber/

나의 풀이(DP - Memoization)

class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = dict()
        def helper(i):
            if i in memo:
                return memo[i]
            if len(nums) - i <= 2:
                memo[i] = max(nums[i:])
                return memo[i]
            memo[i] = max(nums[i] + helper(i + 2), helper(i + 1))
            return memo[i]
        return helper(0)

다른 풀이(DP - Tabulation)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        
        dp = collections.OrderedDict()
        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]