[LeetCode]面试题 17.16. The Masseuse LCCI

A popular masseuse receives a sequence of back-to-back appointment requests and is debating which ones to accept. She needs a break between appointments and therefore she cannot accept any adjacent requests. Given a sequence of back-to-back appoint ment requests, find the optimal (highest total booked minutes) set the masseuse can honor. Return the number of minutes.

Note: This problem is slightly different from the original one in the book.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Accept request 1 and 3, total minutes = 1 + 3 = 4
Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Accept request 1, 3 and 5, total minutes = 2 + 9 + 1 = 12
Example 3:

Input: [2,1,4,5,3,1,1,3]
Output: 12
Explanation: Accept request 1, 3, 5 and 8, total minutes = 2 + 4 + 3 + 3 = 12

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-masseuse-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

python3:

 1 class Solution:
 2     def massage(self, nums: List[int]) -> int:
 3         n = len(nums)
 4         if n == 0:
 5             return 0
 6         
 7         dp0 = 0
 8         dp1 = nums[0]
 9         for i in range(1, n):
10             tdp0 = max(dp0, dp1)
11             tdp1 = dp0 + nums[i]
12             dp0 = tdp0
13             dp1 = tdp1
14         
15         return max(dp0, dp1)