按摩师
难度:
标签:
题目描述
A popular masseuse receives a sequence of back-to-back appointment requests and is debating which ones to accept. She needs a break between appointments and therefore she cannot accept any adjacent requests. Given a sequence of back-to-back appoint ment requests, find the optimal (highest total booked minutes) set the masseuse can honor. Return the number of minutes.
Note: This problem is slightly different from the original one in the book.
Example 1:
Input: [1,2,3,1] Output: 4 Explanation: Accept request 1 and 3, total minutes = 1 + 3 = 4
Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: Accept request 1, 3 and 5, total minutes = 2 + 9 + 1 = 12
Example 3:
Input: [2,1,4,5,3,1,1,3] Output: 12 Explanation: Accept request 1, 3, 5 and 8, total minutes = 2 + 4 + 3 + 3 = 12
代码结果
运行时间: 24 ms, 内存: 16.1 MB
/*
* 思路：
* 由于 Java Stream 不适合直接处理动态规划问题，这里采用传统方法计算后输出结果。
* 1. 使用动态规划解决问题，计算出最长预约时间。
* 2. 用 Stream 对结果进行格式化输出。
*/
import java.util.stream.IntStream;
public class Solution {
public int massage(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[nums.length - 1];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 7, 9, 3, 1};
System.out.println(IntStream.of(solution.massage(nums)).mapToObj(String::valueOf).findFirst().orElse(""));
}
}解释
方法:
动态规划。定义dp数组，其中dp[i]表示考虑前i个预约时的最大总时长。状态转移方程为dp[i] = max(dp[0], dp[1], ..., dp[i-2]) + nums[i]，即当前预约的最大总时长等于前i-2个预约的最大总时长加上当前预约的时长。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法描述中提到的状态转移方程dp[i] = max(dp[0], dp[1], ..., dp[i-2]) + nums[i]的逻辑是如何确保不选择相邻预约的？
▷🦆
在动态规划的实现中，为什么选择初始化dp数组为nums的副本？是否有其他初始化方式？
▷🦆
代码中对于长度小于2的nums数组如何处理？dp数组的初始条件是否能够覆盖所有边界情况？
▷