Fantasy
0%

Leetcode 面试题17.16-按摩师

发表于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题意

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

示例 1：

1
2
3
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

1
2
3
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

1
2
3
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

思路

定义 $dp[i]$ 表示以 $i$ 号预约结尾时的最大服务时长。

首先注意到一定存在 $dp[i] \ge dp[i-2]$ ，因为若 $dp[i]$ 中选择 $i-2$ 号预约时，将有 $dp[i]=dp[i-2]+nums[i]$ 。

此外，当选择了 $i$ 号预约后，$i-1$ 号预约将无法被选择，根据上面结论，$dp[i-2] \ge dp[i-4]$， $dp[i-3] \ge dp[i-5]$，因此状态转移方程为：

注意边界条件，$dp[0]=0$，$dp[i] = nums[i]\space(i \le 2)$。

最终的答案为 $max(dp[n], dp[n-1])$ ，其中 $n$ 为序列长度。因为整个序列的最大服务时长序列中要么包括 $n$ 号预约，要么不包括。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int massage(vector<int>& nums) {
        int n = nums.size();

        if (n == 0)
            return 0;
        if (n == 1)
            return nums[0];
        
        vector<int> dp(n);
        for (int i = 0; i < n; i++) {
            if (i < 2)
                dp[i] = nums[i];
            else if (i == 2)
                dp[i] = dp[i - 2] + nums[i];
            else
                dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i];
        }

        return max(dp[n - 1], dp[n - 2]);
    }
};

此处时间复杂度和空间复杂度均为 $O(n)$ ，由于我们只需要 $dp[n]$ 和 $dp[n-1]$ ，且每个状态的计算最多只涉及到前3项，因此可以用变量代替数组，空间复杂度降低为 $O(1)$ 。