动态规划解决按摩师预约问题——以LeetCode面试题17.16为例
1.题目链接
LeetCode面试题17.16 按摩师
2.题目描述
一个有名的按摩师收到一系列的预约请求，每个预约都可以选择接受或不接受。但相邻的预约不能同时接受。给定一个包含各预约时长的数组 nums，求她能获得的最长总时间。若数组为空，返回0。
3.示例分析
示例1：
输入：[1,2,3,1]
输出：4
解释：接受第1个（时长1）和第3个（时长3）预约，总时长为1+3=4；或接受第2个（2）和第4个（1），总时长为3。因此最大值为4。
示例2：
输入：[2,7,9,3,1]
输出：12
解释：选择第1、3、5个预约，总时长2+9+1=12。
4.算法思路
动态规划状态定义：
f[i]表示接受第i个预约时的最大总时长。g[i]表示不接受第i个预约时的最大总时长。
状态转移方程：
- 若接受第
i个预约，则第i-1个必须未被接受：
f[i] = g[i-1] + nums[i] - 若不接受第
i个预约，则第i-1个可接受或不接受：
g[i] = max(f[i-1], g[i-1])
最终结果：
取 f 和 g 数组最后一个元素的最大值，即 max(f[n-1], g[n-1])。
5.边界条件与注意事项
- 空数组处理： 直接返回0。
- 单元素数组： 直接返回该元素值。
- 数组索引范围： 遍历时需从第2个元素（索引1）开始。
- 状态初始化：
f[0] = nums[0]（选第一个），g[0] = 0（不选第一个）。
6.代码实现
class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if(n == 0) return 0; // 空数组直接返回0vector<int> f(n), g(n);f[0] = nums[0]; // 初始化选第一个的情况g[0] = 0; // 初始化不选第一个的情况for(int i = 1; i < n; i++) {f[i] = g[i-1] + nums[i]; // 当前选，则前一个必须不选g[i] = max(f[i-1], g[i-1]); // 当前不选，前一个可选可不选}return max(f[n-1], g[n-1]); // 最终取最大值}
};
代码解析：
- 时间复杂度： O(n)，遍历数组一次。
- 空间复杂度： O(n)，使用两个数组存储状态；可优化为O(1)（用变量替代数组）。
- 关键点： 通过动态规划维护两个状态，确保每一步的选择满足不相邻条件，最终得到全局最优解。
