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.
Example 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
0 <= nums.length <= 1000 <= nums[i] <= 400Source
from collections import defaultdict
def rob(nums):
"""Recursive approach with memoization"""
def helper(i, arr):
nonlocal n, mydict
if not arr:
return 0
if i not in mydict:
if len(arr) < 3:
mydict[i] = max(arr)
else:
mydict[i] = max(arr[0] + helper(i+2, arr[2::]), helper(i+1, arr[1::]))
return mydict[i]
mydict = defaultdict()
n = len(nums)
return helper(0, nums)
nums = [1,2,3,1]
rob(nums)
4
nums = [2,7,9,3,1]
rob(nums)
12
nums = []
rob(nums)
0
Solve it both recursively and iteratively.
def rob(nums):
"""Dynamic Programming solution"""
if not nums:
return 0
if len(nums) < 3:
return max(nums)
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i, val in enumerate(nums[2:], 2):
dp[i] = max(dp[i-2] + val, dp[i-1])
return dp[-1]
Solve it with 0(1) (i.e. constant) memory.
def rob(nums):
"""Dynamic Programming solution with O(1) memory"""
prev1, prev2, curr = 0,0,0
for val in nums:
curr = max(val + prev2, prev1)
prev2 = prev1
prev1 = curr
return curr