面试题 17.16. 按摩师
思路
典型的动态规划题目，存在多个子问题。这题与打家劫舍一模一样 这边我们设f(n)为接纳前N个客户的时长, a为预约数组 当n = 0的时候，显然f(n) = 0 当n = 1的时候，显然f(n) = a[n] 当n >= 2的时候，f(n) = max(f(n-2) + a[n], f(n-1)) 分2种情况，接纳第n个客户的话，那么就不能接相邻的客户a[n-1]了，所以总数为f(n-2) + a[n] 如果不接纳第n个客户，那么总数就和f(n-1)一样了。我们是为了求最大的解，所以要取2者的最大值。
// 这不就是打家劫舍吗？ func massage(nums []int) int { // 假设她不接第n个人 // n == 1 f(n) = a[n] // n == 2 f(n) = max(a[n], a[n-1]) // f(n) = max(f(n-1), f(n-2)+a[n]) if len(nums) == 0 { return 0 } first, second := 0, nums[0] for i:=1;i<len(nums);i++ { first, second = second, max(first+nums[i], second) } return second } func max(a, b int) int { if a > b { return a } return b }
image-20201130194020286
class Solution: def massage(self, nums: List[int]) -> int: if len(nums) == 0: return 0 first, second = 0, nums[0] for n in nums[1:]: first, second = second, max(first+n, second) return second
image-20201130194844069
