解題思路
動(dòng)態(tài)規(guī)劃：
定義 dp[i][0] 表示第i個(gè)預(yù)約不接，dp[i][1]表示第i個(gè)預(yù)約接将饺。根據(jù)題意，相鄰的預(yù)約不能接。
因此當(dāng)?shù)趇個(gè)預(yù)約不接時(shí)予弧，第i-1個(gè)預(yù)約接不接都可以刮吧，則 dp[i][0] = max(dp[i-1][0], dp[i-1][1])；而當(dāng)?shù)趇個(gè)預(yù)約接受的時(shí)候掖蛤，第i-1個(gè)預(yù)約不能接杀捻，則dp[i][1] = dp[i-1][0]+nums[i]，最后返回max(dp[n][0], dp[n][1])即可蚓庭。
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n)致讥，其中 n 為預(yù)約的個(gè)數(shù)。我們有 2n 個(gè)狀態(tài)需要計(jì)算器赞，每次狀態(tài)轉(zhuǎn)移需要 O(1) 的時(shí)間垢袱，所以一共需要 O(2n)=O(n) 的時(shí)間復(fù)雜度。
空間復(fù)雜度：O(1)港柜，只需要常數(shù)的空間存放若干變量请契。
代碼
class Solution:
def massage(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
dp0 = 0 # 第一個(gè)預(yù)約不接
dp1 = nums[0] # 第一個(gè)預(yù)約接
for i in range(1, n): # 從第二個(gè)預(yù)約開始
tdp0 = max(dp0, dp1) # 第i個(gè)預(yù)約不接，那么第i-1個(gè)預(yù)約可以接夏醉，也可以不接爽锥，取最大值
tdp1 = dp0 + nums[i] # 第i個(gè)預(yù)約接，那么第i-1個(gè)預(yù)約不可以接
dp0 = tdp0
dp1 = tdp1
return max(dp0, dp1)
