題目出處
難度
Medium
個人範例程式碼
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
dp = []
for i in range(len(nums)):
if i == 0:
dp.append(nums[0])
elif i == 1:
dp.append(max(nums[0], nums[1]))
else:
dp.append(max(dp[i-1], dp[i-2] + nums[i]))
# print(dp)
return dp[-1]
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
算是陽春的 DP 問題，
- 主要目標：dp[i] = max(dp[i-2]+A[i], dp[i-1])
- dp[0] = A[0]
- dp[1] = max(A[0], A[1])
input handling
處理 input 沒有房子與 input 只有一棟房子的情況
- 沒有房子，return 0
- 只有一棟房子，return 那一棟房子
Boundary conditions
for 來控制範圍