Leetcode # 213. House Robber II
https://leetcode.com/problems/house-robber-ii
Solution
| _rob() | := | 必定搶最後一間的收益 |
| 結果 | := | max(搶最後一間, 不搶最後一間) |
| = | max(搶最後一間 and 不搶第一間, 不搶最後一間) | |
| = | max(_rob(nums[1:]), robs(nums[:-1])) |
Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) < 2:
return sum(nums)
def _rob(start, end):
DP = [0, nums[start]] # don't rob or rob
for num in nums[start + 1:end + 1]:
DP = [DP[1], max(num + DP[0], DP[1])]
return DP[1]
return max(
_rob(1, len(nums) - 1), # rob last house
_rob(0, len(nums) - 2) # don't rob last house
)
Last Updated on 2023/08/16 by A1go
