[Python] Leetcode 198. House Robber (Medium)

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

House Robber - LeetCode

 

DP의 대표적인 유형 입문 문제입니다.

집을 연속으로 털지 못한다는 것에서 N번째 집을 털때의 최대값은 N-2번째 집을 털고 N번째 집을 터는 것과 N번째 집을 털지 않는 경우 (즉 N-1번째 집에서의 최댓값) 두 값중 큰 값을 고르게 됩니다.

 

class Solution:
    def rob(self, nums: list) -> int:
        
        dp = [0] * (len(nums) + 1)
        dp[0] = 0
        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1],dp[i-2]+ nums[i-1])

        return dp[-1]


input = [[1,2,3,1],[2,7,9,3,1],[1]]
for i in input:
    print(Solution().rob(i))