題目出處
難度
Medium
個人範例程式碼
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp_no_first = [0, nums[1]]
dp_contains_first = [nums[0], max(nums[0], nums[1])]
return max(self.get_max_rob(nums, dp_no_first), self.get_max_rob(nums[:-1], dp_contains_first))
def get_max_rob(self, nums, dp):
for i in range(2, len(nums)):
dp.append(max(dp[i-2] + nums[i], dp[i-1]))
return dp[-1]
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
- 這題的前一題為沒有循環房子的版本，可參考：
https://wongwongnotes-github-io.pages.dev/python/python_leetcode/leetcode-python-198/
相比上一題，這一題因為房子的排列會變成一個圈，因此我們把頭尾的關係分為兩段來考慮，
- 不包含 0，一路算到 n
- 包含 0，一路算到 n-1
input handling
處理 input 沒有房子與 input 只有一棟房子的情況
- 沒有房子，return 0
- 只有一棟房子，return 那一棟房子
Boundary conditions
for 來控制範圍