前往此题

解题思路

像这种不同阶段之间都有联系的题一般都能用动态规划来解

状态设计

题目中按摩师存在不接预约和接预约两种情况，我们在做动态规划的时候需要将两种情况都计算进去。

• dp[i][0] 代表当天不接受预约的累积最大时长
• dp[i][1] 代表当天接受预约所累积的最大时长

状态转移方程

上面我们也分析了，此题中只有两种状态，接下来对这两种状态分析出转移方程

1. 今天接受预约：代表昨天肯定没有接受预约，所以只需要将昨天的时长加上今天的时长

   dp[i][1] = dp[i-1][0] + nums[i]

2. 今天不接受预约：代表昨天接受了预约或者没接受预约，我们取这两者的最大值即可

   dp[i][0] = max(dp[i-1][0], dp[i-1][1])

边界

确定了状态转移方程，我们知道了元素之间的联系只是i与i-1之间产生的，所以边界就是第一天：

• dp[0][0] = 0
• dp[0][1] = nums[0]

最后再返回最后一天的时长，取两种状态的最大值即可

代码

class Solution:
    def massage(self, nums: List[int]) -> int:
        N = len(nums)
        if N == 0: return 0
        
        dp = [[0]*2]*N
        dp[0][0] = 0
        dp[0][1] = nums[0]
        
        for i in range(1, N):
          dp[i][0] = max(dp[i-1][0], dp[i-1][1])
          dp[i][1] = dp[i-1][0] + nums[i]
        return max(dp[N-1][0], dp[N-1][1])

代码优化

上面用的数组，空间复杂度为O(n)，我们可以通过两个变量来实现O(1)的空间复杂度

class Solution:
    def massage(self, nums: List[int]) -> int:
        N = len(nums)
        if N == 0: return 0

        dp0 = 0
        dp1 = nums[0]

        for i in range(1, N):
            tdp0 = max(dp0, dp1)
            tdp1 = dp0 + nums[i]
            dp0 = tdp0
            dp1 = tdp1
        return max(dp0, dp1)