Letcode 9월 14일

질문 -

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police

예 =
"""
입력:nums=[1,2,3,1]
산출: 4
설명: 먼저 집 1(돈=1)을 털고, 그 다음에 집 3(돈=3)을 털는다.
네가 약탈할 수 있는 총 금액은 1+3=4이다.
"""
직감 - 탐욕스러울 수도 있다. 즉, 세 가지 가능성 중에서 최대치를 선택한 다음 계속 전진하고, 다른 세 가지 가능성 중에서 최대치를 선택하는 것이다.
그러나 미래의 가치관이 무엇인지 모르기 때문에 우리는 몇 가지 사례를 놓칠 수 있다.
다음 시나리오 고려 - [2,4,8,40]만약 우리가 탐욕스럽다면, 우리는 8을 선택할 것이다.그러나 만약 우리가 4를 선택한다면 우리도 40을 선택할 수 있다. 결과는 44가 될 것이다.
그래서 탐욕은 여기서 통하지 않는다.우리는 모든 가능성/상태를 열거해야 한다.그래서 우리는 이렇게 할 것이다.우리는 회고록을 사용하여 시간의 복잡도를 낮출 것이다.우리가 사용하는 것은 비망록이기 때문에, 우리는 그것을 dp 솔루션이라고 부른다.
솔루션 -

class Solution:
    def rob(self, nums: List[int]) -> int:
        cache = {}
        def dp(idx):
            if idx < 0:
                return 0
            else:
                res = cache.get(idx, None)
                if res is not None:
                    return res
                else:
                    res = max(dp(idx-1), dp(idx-2) + nums[idx])
                    cache[idx] = res
                    return res
        return dp(len(nums)-1)