Challenge
The array nums represent the value inside each house. What is stopping you to rob everything is that you cannot rob two consecutive houses without triggering the alarm. Determine the maxium amout of money you can rob without triggering the alarm.
Solution 1 - Recursion
class Solution:
def helper(self, index, nums, val):
if index > len(nums)-1:
self.m = max(self.m, val)
return
self.helper(index+1, nums, val)
self.helper(index+2, nums, nums[index] + val)
def rob(self, nums: List[int]) -> int:
self.m = float("-inf")
self.helper(0, nums, 0)
return self.m
Time Complexity: O(2^n)
Solution 2 - Dynamic Programming
def houseRobber(nums):
res = []
dp = [0 for i in range(len(nums))]
if not nums:
return 0
if len(nums) < 3:
return max(nums)
dp[0] = nums[0]
print(dp)
if nums[1] > nums[0]:
dp[1] = nums[1]
else:
dp[1] = nums[0]
for i in range(2, len(nums)):
val = max(dp[i-1], dp[i-2] + nums[i])
dp[i]= val
return dp[-1]