리트코드-198. House Robber

문제

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

풀이

해당 문제는 도둑이 훔칠 수 있는 가장 큰 금액을 구하는 문제로, 바로 옆집은 훔칠 수 없다는 조건이 붙어있다.
따라서 리스트를 차례대로 탐색하면서 해당 인덱스에서 나올 수 있는 최대값을 구하면 되는 문제다.
즉, DP 문제이다.

• dp[n]에서의 최대값은 nums[n] += nums[n-2] + nums[n-3]이다. 즉, 바로 옆집은 안되니 하나나 두개 떨어진 이전 집에서 온 경우를 의미한다.
• 나는 여태까지 DP 문제를 리스트로 풀이했다. 하지만 찾아보니 Dict를 사용한 경우도 많고(파이썬 3.7 버전 이상) collections.OrderedDict를 사용한 경우도 많았다(3.6 이하 버전)

코드

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        
        for i in range(2, len(nums)):
            if i ==2:
                nums[2] += nums[0]
                continue
            nums[i] += max(nums[i-2], nums[i-3])
        return max(nums)