描述
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
示例
输入： [2,1,4,5,3,1,1,3] 输出： 12 解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
from typing import List from functools import lru_cache class Solution: def massage(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] if len(nums) == 0: return 0 ans = [0] * len(nums) @lru_cache(10000) def dynamic_programming(index): if index == 0: return ans[0] elif index == 1: return ans[1] else: ans[index] = max(dynamic_programming(index - 1), dynamic_programming(index - 2) + nums[index]) return ans[index] ans[0] = nums[0] ans[1] = max(nums[0], nums[1]) dynamic_programming(len(nums) - 1) return max(ans) if __name__ == '__main__': cal = Solution() arr = [2, 1, 3, 4, 1, 2, 1, 5, 4, 1, 4, 5, 6, 3, 3, 1, 6, 3, 6] print(cal.massage(arr))dp思路：因为不能连续按摩，所以要想取得（i）的最优解需要将"（i-1）的最优解"和"（i-2）的最优解+当前value"进行比较。
比较坑的是nums传参竟然可以是空List...
