198. House Robber
[Easy] “Police 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."
Python3:
# recursion + memoization
def rob(self, nums: List[int]) -> int:
memo = [-1] * len(nums)
return self.plan(nums, len(nums) - 1, memo)
def plan(self, nums, i, memo):
if i < 0:
return 0
elif memo[i] >= 0:
return memo[i]
else:
rob_curr = self.plan(nums, i - 2, memo) + nums[i]
rob_next = self.plan(nums, i - 1, memo)
outcome = max(rob_curr, rob_next)
memo[i] = outcome
return outcome