leetcode 198(dp), 213(dp), 337(dp)

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

n>=3일때 n의 최대값은 max(n-2번째집까지의 최대값 or n-3번째집까지의 최대값) + 현재집이다.

이렇게 만들고 풀어준다.

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        elif len(nums) <= 2:
            return max(nums)
        elif len(nums) == 3:
            return max(nums[0]+nums[2], nums[1])
        
        dp = [0 for i in xrange(len(nums))]
        dp[0] = nums[0]
        dp[1] = nums[1]
        dp[2] = max(nums[0]+nums[2], nums[1])
        for i in xrange(3, len(nums)):
            dp[i] = max(dp[i-2], dp[i-3]) + nums[i]
        return max(dp)

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

위와 같은데 이번엔 조건이 까다롭다. 첫집과 끝집이 이어져 있다. 즉 끝집을 계산할때 이전 계산 과정까지 첫집이 포함되었는지까지 고려해야한다. 그런데 어차피 첫집이나 끝집 둘중 하나만 포함되어있으면 되므로 nums[1:]과 nums[:-1]둘의 값을 구하고 그중에 큰걸 고르면 된다.

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        elif len(nums) <= 3:
            return max(nums)

        def rrob(nums):
            dp = [0 for i in xrange(len(nums))]
            dp[0] = nums[0]
            dp[1] = nums[1]
            dp[2] = max(nums[0] + nums[2], nums[1])
            for i in xrange(3, len(nums)):
                dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i]
            return max(dp)

        return max(rrob(nums[1:]), rrob(nums[:-1]))

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

이번엔 집이 이진 트리 모양이다.

최대값을 구하는 방법은 서브트리에서 max(현재 루트의 값을 포함한 값, 현재 루트의 값 포함하지 않은 값) 이다.

현재 루트의 값을 포함한 값 == 양쪽 손자들의 값 + 루트의 값 이고

현재 루트의 값을 포함하지 않은 값 == 양쪽 자손들의 값중 최대값이다.

함수를 선언하고 현재 루트 기준으로 (현재 루트의 값을 포함한 값, 현재 루트의 값 포함하지 않은 값) 두개를 리턴하도록 하고 재귀를 돈다.

설명은 https://leetcode.com/problems/house-robber-iii/discuss/376297/Python3-Dynamic-Programming-%2B-Depth-First-Search 여기 잘 되어있다.

class Solution(object):
    def rob(self, root):
        def dfs(root):
            if not root:
                return 0,0
            left = dfs(root.left)
            right = dfs(root.right)
            return root.val + left[1] + right[1], max(left) + max(right)  # [0] = 현재 루트를 포함한 값 == 손자들의 최대값 + 루트의 값, [1] = 현재 루트를 포함하지 않은값 == 왼쪽,오른쪽 자손의 최대값
            
        return max(dfs(root))