LC 213 - House Robber II
Question
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
1
2
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
1
2
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 3:
1
2
Input: nums = [1,2,3]
Output: 3
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000
Links
Question here and solution here
Solution
concept
memoization
The easiest way to solve this with memoization is using 2 loop to calculated 2 robbing sequences:
- from 1st house to the 2nd-to-last house
- from 2nd house to the last house and then we choose the max of the 2, because you cannot rob the first and last house
bottom up solution
Using the same idea, we can reuse solution from [[198. House Robber]] and run it two times also and use the max to get the answer.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution:
"""
top down dp: memoization
2 robbing sequences
"""
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
dp_1 = [-1] * (len(nums) - 1)
dp_2 = [-1] * (len(nums) - 1)
def dfs(i, arr, dp):
if i >= len(arr):
return 0
if dp[i] != -1:
return dp[i]
dp[i] = max(arr[i]+dfs(i+2, arr, dp), dfs(i+1, arr, dp))
return dp[i]
# 1st house to 2nd-to-last
start_1st_house = dfs(0, nums[:-1], dp_1)
# 2nd house to last
start_2nd_house = dfs(0, nums[1:], dp_2)
return max(start_1st_house, start_2nd_house)
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) <= 2:
return max(nums)
dp_1 = [0]*(len(nums) - 1)
dp_2 = [0]*(len(nums) - 1)
# rob first to second last
dp_1[0] = nums[0]
dp_1[1] = max(nums[0],nums[1])
for i in range(2, len(dp_1)):
dp_1[i] = max(nums[i] + dp_1[i-2], dp_1[i-1])
# rob second to last
dp_2[0] = nums[1]
dp_2[1] = max(nums[1], nums[2])
for i in range(2, len(dp_2)):
dp_2[i] = max(nums[i+1] + dp_2[i-2], dp_2[i-1])
return max(dp_1[-1], dp_2[-1])
class Solution:
"""
bottom up dp
space optimised
"""
def rob(self, nums: List[int]) -> int:
def rob_helper(nums):
"""
rob house 1 solution
"""
rob_1, rob_2 = 0, 0
for n in nums:
tmp = max(rob_2, rob_1 + n)
rob_1 = rob_2
rob_2 = tmp
return rob_2
# 1st house to 2nd-to-last
ans_1 = rob_helper(nums[:-1])
# 2nd house to last house
ans_2 = rob_helper(nums[1:])
return max(nums[0], ans_1, ans_2)
Complexity
time: $O(n)$
space: $O(n)$