[LeetCode][Python3] 198. House Robber

Problem :

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

My Solution :

class Solution:

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

dp = [0] * (len(nums)+1)

for i, n in enumerate(nums, 1):

dp[i] = max(n + dp[i-2], dp[i-1])

return dp[-1]

Comment :

전형적인 DP 문제이고 예전에 HackerRank에서 동일한 유형의 문제를 풀어봤기 때문에 쉽게 풀 수 있었다.

아래는 메모리 절약 버전

My Solution2 :

class Solution:

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

a = b = 0

for n in nums:

a, b = b, max(n + a, b)

return b