# Python solution with detailed explanation

• Solution with discussionhttps://discuss.leetcode.com/topic/80721/python-solution-with-detailed-explanation

Memoization:

• Use another variable first which indicates if first house is included or not in the current DFS path.
• Based on first, at index N-1, we will set use (the case where we rob a house) to 0 or nums[i].
• Caching will be 2D. At index i, we now ask what is the maximum money we can rob given we robbed house 0 or not.
``````class Solution(object):
def helper(self, i, nums, cache, first):
N = len(nums)
if i >= N:
return 0
if i in cache and first in cache[i]:
return cache[i][first]
cache.setdefault(i, {})
if i == 0:
use, not_use = nums[i]+self.helper(i+2, nums, cache, True), self.helper(i+1, nums, cache, False)
elif i + 1 == N and first:
use, not_use = 0, self.helper(i+1, nums, cache, first)
else:
use, not_use = nums[i]+self.helper(i+2, nums, cache, first), self.helper(i+1, nums, cache, first)
cache[i][first] = max(use, not_use)
return cache[i][first]

def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = {}
return self.helper(0, nums, cache, False)
``````

Dynamic Programming

``````class Solution(object):
def sub_rob(self, nums, lo, hi):
"""
:type nums: List[int]
:rtype: int
"""
result = prev_prev = prev = 0
for idx in range(lo, hi+1):
result = max(prev_prev+nums[idx], prev)
prev_prev = prev
prev = result
return result

def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return sum(nums)
return max(
self.sub_rob(nums, 0, len(nums)-2),
self.sub_rob(nums, 1, len(nums)-1)
)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.