House Robber Problem
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 systems connected, and it will automatically contact the police if two adjacent houses are 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 them tonight without alerting the police.
Solution: Recursive
class Solution:
def recursive(self, i, nums):
if i ==0: return nums[0]
max_val =-1
max_val = max(max_val, self.recursive(i-1, nums))
for j in range(i-2, 0, -1):
max_val = max(max_val, self.recursive(j, nums)+ nums[i-1])
return max_val
Time Complexity
The time complexity of the given recursive solution is exponential, specifically O(2^n), where n is the value of i. This is because, for each house i, the algorithm explores two recursive branches: one where the current house is robbed and one where it is not robbed.
The number of recursive calls grows exponentially with the value of i, leading to an exponential time complexity.
Space Complexity
The space complexity is determined by the maximum depth of the recursion tree, which is also exponential. For each level of recursion,
additional space is used for the call stack. Therefore, the space complexity is O(2^n) as well.
Solution: Recursive (2)
class Solution:
def robber(self, nums):
if len(nums) ==0:
return 0
def dfs(i, count):
if i >= len(nums):
return count
count =max(count,dfs(i+1, count), dfs(i+2, count+nums[i]))
return count
return dfs(0, 0)
Time Complexity
The time complexity of the given solution is exponential O(2^n), where n is the length of the input array nums. This is because, for each house, the algorithm explores two recursive branches: one where the current house is robbed and one where it is not robbed. The number of recursive calls grows exponentially with the size of the input array, leading to an exponential time complexity.
Space Complexity
The space complexity is O(n) due to the maximum depth of the recursion tree. The length of the input array determines the depth of the recursion, and for each depth level, the algorithm uses additional space for the recursive call stack.
Therefore, the space complexity is linear with respect to the size of the input array.
Here's an alternative approach to writing the above code. In my view, this is easier to understand. The code is more concise because I do not use inner methods that can complicate understanding it.
class Solution:
def robber(self, nums):
if nums ==[]:
return 0
max_val =-1
for i in range(len(nums)):
max_val =max(max_val, nums[i] + self.robber1(nums[i+2:]), self.robber1(nums[i+1:]))
return max_val
Solution: Top-Down Dynamic Programming (Memoization)
class Solution:
def robber_top_down(self, nums):
dp ={}
if nums ==[]:
return 0
max_val =-1
for i in range(len(nums)):
if i in dp:
return dp[i]
max_val =max(max_val, nums[i] + self.robber_top_down(nums[i+2:]), self.robber_top_down(nums[i+1:]))
dp[i]=max_val
return dp[len(nums)-1]
Time Complexity
The time complexity of the given solution is O(n^2), where n is the length of the input array nums. This is because, for each house, the algorithm explores two recursive branches: one where the current house is robbed and one where it is not robbed.
The number of recursive calls is reduced by memoization (using the dp dictionary), but there is still a quadratic number of subproblems due to the two nested recursive calls.
Space Complexity
The space complexity is O(n) due to the memoization using the dp dictionary. The maximum depth of the recursion tree is limited to the length of the input array nums, and for each depth level, the algorithm uses additional space to store intermediate results in the dp dictionary.
Therefore, the space complexity is linear with respect to the size of the input array.
Solution: Bottom-Up Dynamic Programming
class Solution:
def bottom_up(self, nums):
n = len(nums)
s ={}
s[0] = nums[0]
s[1] = max(nums[0], nums[1])
for i in range(2, n):
s[i] = s[i-1]
for j in range(i-2, -1, -1):
s[i] = max(s[i], s[j]+nums[i])
return s[n-1]
Time Complexity
The time complexity of the given solution is O(n^2), where n is the length of the input array nums. This is because there is a nested loop structure: the outer loop runs in O(n), and for each iteration of the outer loop, the inner loop can run up to O(n) times, resulting in an overall time complexity of O(n^2).
Space Complexity
The space complexity is O(n) as the dynamic programming array s has a length of n, where n is the length of the input array nums.
Each entry in the array stores the maximum sum up to that point, contributing to the overall space complexity of O(n).
Solution: Optimized Bottom-up Dynamic Programming
We can optimize the bottom-up solution further to give a solution whose runtime is O(n)
class Solution:
def bottom_up_optimized(self, nums):
n = len(nums)
s ={}
s[0] = nums[0]
s[1] = max(nums[0], nums[1])
for i in range(2, n):
s[i] = s[i-1]
s[i] =max(s[i-1], nums[i]+s[i-2])
return s[n-1]
sol = Solution()
print("house robber bottom-up optimized::", sol.bottom_up_optimized([1,2,3,4,5]))