头脑风暴：按摩师

头脑风暴：按摩师

题目

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

示例1：

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

示例2：

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

示例3：

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

解题思路

根据题意，我们可以使用动态规划的方法来解答此题。

首先确定 dp 数组的含义：

dp[i][0] 表示：区间 [0..i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长； dp[i][1] 表示：区间 [0..i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长。

第二步，确定动态转移方程，由于按摩师不能连续接活，于是我们需要对预约进行分类讨论：

今天不接受预约：假如昨天按摩师不接受预约，或者是昨天接受了预约，那么取二者最大值，即：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])； 今天接受预约：需要从昨天不接受预约转移而来，加上今天的时常，即：dp[i][1] = dp[i - 1][0] + nums[i]。

第三步初始化 dp 数组：如果第一天不接受预约，那么 dp[0][0] = 0, 如果第一天接受预约 dp[0][1] = nums[0];

代码实现

class Solution { public int massage(int[] nums) { int len = nums.length; if(len == 0){ return 0; } if(len == 1){ return nums[0]; } int[][] dp = new int[len][2]; dp[0][0] = 0; dp[0][1] = nums[0]; for(int i = 1; i < len; i++){ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]); dp[i][1] = dp[i-1][0] + nums[i]; } return Math.max(dp[len-1][0], dp[len-1][1]); }}

最后

时间复杂度：O(n)，其中 n 为预约的个数。空间复杂度：O(1)，只需要常数的空间存放若干变量。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。