[Leetcode] 198. House Robber

문제

https://leetcode.com/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked

풀이

dp[k]를 "k번째 house까지의 최대 rob 합" 으로 정의하고, recursive formula를 세워 값을 채워나갔다. k번째 집을 포함할 때와 포함하지 않은 경우에 대해 max값을 구하도록 했다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        if n == 1:
            return nums[0]

        dp = [0]*n # dp[k]: k번쨰 house까지의 최대 rob 합

        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for idx in range(2,n):
            dp[idx] = max(dp[idx-1], dp[idx-2]+nums[idx]) # idx를 포함할때, 포함하지 않을때
        
        return dp[n-1]