LeetCode 풀기 - 198. House Robber

198. House Robber

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

House Robber - LeetCode

문제)

솔루션1) - Dynamic Programming

i번째 집에 도착했을 때 최대로 훔칠 수 있는 값을 구하는 것입니다.

 

Intuition:

• 도둑이 순서대로 집을 털면서 i번째 도착했을 때 max를 구하는 문제
• 0번째 집에 도착했을 때는 nums[0]
• 1번째 집에 도착했을 때는 nums[0], nums[1] 둘 중에서 큰 값
• 2번째 집에 도착했을 때는 nums[1] 집의 값이거나, nums[0] + num[2] 중 더 큰 값
• 위를 조금 더 풀어서 설명하면, 도둑이 i번째 집에 있을 때 최대 값은 i-1번째 집까지 훔쳤을 때의 값이거나 or i-2번째 집에서 훔친 값과 i번째 집의 값을 더한 값 중 더 큰 값에 해당
• 이름 점화식으로 풀어쓰면, 
  • f(k) = max(f(k-2) + nums[k], f(k-1))

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Dynamic Programming
        # 점화식:
        #   f(0) = nums[0]
        #   f(1) = max(nums[0], nums[1])
        #   f(2) = max(f(0) + nums[2], f(1))
        #   ...
        #   f(k) = max(f(k-2) + nums[k], f(k-1))
        
        if len(nums) == 1: return nums[0]
        nums[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            nums[i] = max(nums[i-2] + nums[i], nums[i-1])
            
        return nums[-1]