House Robber || Leetcode
Problem can be found here
Determine the maximum amount of money that can be stolen from a series of houses (each represented by indexes of the array) without robbing any two consecutive houses.
This is a tricky problem that requires thorough understanding.
Brute Force / Intuition
This is problem that require a robber to make a decision, therefore you could create a decision tree out of the problem.
given array: [a, b, c, d, e, f, g]
array = [a, b, c, d, e, f, g]
index = [0, 1, 2, 3, 4, 5, 6]where index of array is house number while value at index (alphabet character) = loot
Where do you start?
You could start from anywhere but should you?
Consider starting from the right side, meaning if you loot at index 0, skip index 1. You can go to any index except 1. The tree below shows the full decision tree.
combination from index 0:
- a + c + e + g
- a + c + f
- a + c + g
- a + d + e + g
- a + d + e + f
- a + d + f
- a + d + g
- a + e + g
combination from index 1:
- b + d + f
- b + e + g
- b + f
combinations for looting from index 2:
- a + c + e + g
- a + c + f
- a + c + g
array = [a, b, c, d, e, f, g]
index = [0, 1, 2, 3, 4, 5, 6]combinations for looting from index 3:
- a + d + f
- b + d + f
- a + d + g
- b + d + g
combinations for looting from index 4:
- a+ c + e + g
- b + e + g
combinations for looting from index 5:
- a + c + f
- b + d + f
combinations for looting from index 6:
- a + c + e + g
- b + d + g
CONCLUSION: When you examine the array, notice that each combination is a subset of robbing from either index 0 or 1. In simpler terms, focus on the calculations as you move forward, and there’s no need to create separate binary trees for each house. Therefore the solution boils down to a binary choice which is recursive.
ANSWER:
def find_max(...)
if (i >= length_of_array): return 0
include = array[i] + find_max(array[i+2:])
exclude = find_max(array[i+1:])
return Math.max(include, exclude)Top Down solution: Time = O(2^n), Space= O(n)
class Solution:
def rob_helper(self, idx):
if idx >= self.n: return 0
include = self.nums[idx] + self.rob_helper(idx+2)
exclude = self.rob_helper(idx+1)
return max(include, exclude)
def rob(self, nums: List[int]) -> int:
self.nums = nums
self.n = len(nums)
return self.rob_helper(0)Dynamic Programming — Memoised Solution: Time = O(n), Space = O(n)
Avoid redundant calculations by storing and recalling previously computed answers using memoization.
memo = An array of size n initialised to -1
class Solution:
def rob_helper(self, idx):
if idx >= self.n:
return 0
if self.memo[idx] != -1:
return self.memo[idx]
include = self.nums[idx] + self.rob_helper(idx+2)
exclude = self.rob_helper(idx+1)
self.memo[idx] = max(include, exclude)
return self.memo[idx]
def rob(self, nums: List[int]) -> int:
self.nums = nums
self.n = len(nums)
self.memo = [-1] * self.n
return self.rob_helper(0)Dynamic Programming — Bottom Up Solution: Time = O(n), Space = O(1)
what the question really cares about is the max not the actual path.
given:
array = [a, b, c, d, e, f, g]
index = [0, 1, 2, 3, 4, 5, 6]in the bottom up we to find the max at any index:
max at index 0 = a
max at index 1 = b
max so far or latest max at index 2 = max(b, a + c)
max at index3 = max(latest_max, b+d ) = latest_max
therefore:
max at index 3 = max(include, exclude) = max(include, latest_max)
where:
include = max([a, b]) + d = max at index 1 + d= prev_max + d
exclude = max at index 2 = latest_max
Using the nums array
class Solution:
def rob(self, nums: List[int]) -> int:
prev_max = 0
for i in range(1, len(nums)):
nums[i] = max(nums[i-1], prev_max+nums[i])
prev_max = nums[i-1]
return nums[-1] Using two variables
class Solution:
def rob(self, nums: List[int]) -> int:
prev_max = 0
latest_max = 0
for n in nums:
temp = max( latest_max, (prev_max+n) )
prev_max = latest_max
latest_max = temp
return latest_max