198. House Robber - python3

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.

My Answer 1: Wrong Answer

class Solution:
    def rob(self, nums: List[int]) -> int:
        result1 = 0
        result2 = 0
        for i in range(0, len(nums)):
            if i % 2 == 0:
              result1 += nums[i]
        for i in range(0, len(nums)):
            if i % 2 != 0:
              result2 += nums[i]
            
        if result1 > result2:
            return result1
        else:
            return result2

처음엔 그냥 한자리 건너뛰어서만 구하는거아냐? 싶어서
짝수번째 idx 들의 합이랑 홀수번째 idx 들의 합을 각각 구해서 둘중에 큰걸 return 했는데 아녔음

문제를 제대로 읽자...^^

Other Answer 1: (Runtime: 28 ms / Memory Usage: 14.3 MB)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0 
        
        if len(nums) <= 2:
            return max(nums)
        
        rob = [0]*len(nums) # keeps the maximum gain the robber can have so far while going through the houses.  
        rob[0] = nums[0] # since these houses are next to each other, its a given that they are the base case we use to decide whether to start at the beginning or not.
        rob[1] = nums[1]
            
        for i in range(1, len(nums)): # dynamically deciding which of the options works best, taking my gains from the last house or to combine current house's potential gains with that of two houses down. 
            rob[i] = max(rob[i-1], nums[i] + rob[i-2])
            
        return rob[-1]

재귀를 사용한 답
rob 는 누적 합의 최대값 리스트

rob[i] = max(rob[i-1], nums[i] + rob[i-2]) => 이부분을 통해서 한칸 떨어진 집털기 조건과 최대값 구하기 조건 둘다 만족하게 됨

ex. nums = [2,7,9,3,1]
=> rob = [7,11,11,12]

Why?

• 7: 2 < 7
• 11: 7 < 11 (9+2)
• 11: 10 (3+7) < 11 (9+2)
• 12: 11 (9+2) < 12 (9+2+1)

Other Answer 2: (Runtime: 32 ms / Memory Usage: 14.2 MB)

class Solution:
    def rob(self, nums: List[int]) -> int:
        future = deque((0,0), 2)
        for i in range(len(nums)-1, -1, -1):
            future.appendleft(max(nums[i] + future[1], future[0]))
        return future[0]

deque 데크: 양방향에서 데이터를 처리할 수 있는 구조
(참고: https://excelsior-cjh.tistory.com/96)

이거도 재귀 쓴거랑 논리는 비슷해보인다
차이점은 얘는 리스트의 끝부터 비교해서 deque 의 맨 왼쪽(앞자리)에 최대값을 넣는다.
여기선 젤 첫번째가 최대값이라면 재귀는 리스트의 젤 마지막이 최대값인 것