House Robber II
- 2 min read
- LC-Medium
- Dynamic Programming
3 years ago
Solution
Similar to House Robber I, but you just have to run the dfs function on two subarrays: one without the first element, and one without the last element. Look at this picture to understand:
We have to reset memo in between the subsequent calls because it's an different problem entirely.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def rob(self, nums: List[int]) -> int:
memo = {}
def dfs(nums, i=0):
if i >= len(nums):
return 0
if i == len(nums) - 1:
return nums[-1]
if i not in memo:
memo[i] = max(nums[i] + dfs(nums, i + 2), dfs(nums, i + 1))
return memo[i]
res1 = dfs(nums[1:])
memo = {}
res2 = dfs(nums[:-1])
return max(res1, res2)
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
last_val = nums.pop()
dp1 = [0] * (n + 1)
dp2 = [0] * (n + 1)
for i in range(n - 2, -1, -1):
dp1[i] = max(nums[i] + dp1[i + 2], dp1[i + 1])
nums.append(last_val)
nums.pop(0)
for i in range(n - 2, -1, -1):
dp2[i] = max(nums[i] + dp2[i + 2], dp2[i + 1])
return max(dp1[0], dp2[0])