House Robber II
Statement
A robber plans to rob houses along a street. The houses are arranged in a circle, so the first and last houses are neighbors. The robber cannot rob adjacent houses because they have security alarms installed. Given an array money that represents the amount of money in each house, find the maximum amount the robber can steal without alerting the police.
Constraints
- 1 ≤
money.length()≤ 10³ - 0 ≤
money[i]≤ 10³
Solution
"""
production algorithm
"""
class Solution:
def house_robber(self, money):
"""
time complexity O(n)
space complexity O(n)
"""
if len(money) == 1:
return money[0]
return max(
self.house_robber_helper(money[:-1]),
self.house_robber_helper(money[1:]))
def house_robber_helper(self, money):
"""
time complexity O(n)
space complexity O(n)
"""
n = len(money)
memo = [0 if k == 0 else None for k in range(n + 1)]
for k in range(1, n + 1):
if k - 2 < 0:
memo[k] = max(money[k - 1], memo[k - 1])
else:
memo[k] = max(money[k - 1] + memo[k - 2], memo[k - 1])
return memo[n]"""
unit tests
"""
from unittest import TestCase
from algorithms.dynamic_programming.house_robber_2.solution import Solution
class SolutionTestCase(TestCase):
def test_one_house(self):
# Given
money = [33]
solution = Solution()
# When
actual = solution.house_robber(money)
# Then
expected = 33
self.assertEqual(actual, expected)
def test_first_house_included(self):
# Given
money = [38, 11, 17, 35, 33, 15, 32, 31, 18]
solution = Solution()
# When
actual = solution.house_robber(money)
# Then
expected = 120
self.assertEqual(actual, expected)
def test_first_house_excluded(self):
# Given
money = [11, 38, 17, 35, 33, 15, 32, 31, 12]
solution = Solution()
# When
actual = solution.house_robber(money)
# Then
expected = 119
self.assertEqual(actual, expected)
def test_last_house_included(self):
# Given
money = [17, 35, 33, 15, 32, 31, 19, 12, 38]
solution = Solution()
# When
actual = solution.house_robber(money)
# Then
expected = 124
self.assertEqual(actual, expected)
def test_last_house_excluded(self):
# Given
money = [17, 37, 33, 15, 32, 31, 11, 39, 12]
solution = Solution()
# When
actual = solution.house_robber(money)
# Then
expected = 122
self.assertEqual(actual, expected)Strategy
Dynamic Programming.
Explanation
The first and last houses along the street are neighbors. In order to prevent including the first and last house together in calculations, they array is sliced in to two subarrays: a subarray of the houses without the last house, and a subarray of the houses without the first house. So then the sliced arrays are non-circular, and are operated on separately. The maximum of the result of the separate calculations is the maximum money that can be robbed.
A helper function is used to calculate the maximum that can be robbed in each subarray. The helper function uses a 1-D matrix, whose dimension is the length of the subarray, to maintain the optimal solution for lengths of the subarray seen so far. In the trivial case, where the length of the subarray is 0, the optimal solution is 0. Then, iteration of the lengths of the subarray occurs. The optimal solution for smaller lengths of the subarray are used to find the optimal solution for larger lengths of the subarray. Iteration ends when the optimal solution has been found for the full length of the subarray.
Notice, that the problem has optimal substructure, i.e. the optimal solution of a larger length of the subarray can be found from the optimal solution of a smaller length of the subarray. Also notice, that the problem has overlapping subproblems, i.e. the optimal solution of a smaller length of the subarray can be reused to find the optimal length of distinct larger lengths of the subarray. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.
Time Complexity
Let n be the length of the array. Then the time complexity of the algorithm is O(n).
Space Complexity
The auxiliary space complexity of the algorithm is O(n).
