「动态规划」当小偷改行去当按摩师，会发生什么？

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

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[i]表示，选择完i位置之后，此时的最长预约时长。再细分为：

• 用f[i]表示，接受i位置的预约之后，此时的最长预约时长。
• 用g[i]表示，不接受i位置的预约之后，此时的最长预约时长。

推导状态转移方程：

• 如果接受i位置的预约，那么就不能接受i - 1位置的预约。所以，接受i位置的预约之后的最长预约时长，就等于不接受i - 1位置的预约之后的最长预约时长加上i位置的预约的时长，即f[i] = g[i - 1] + nums[i]。
• 如果不接受i位置的预约，那么既可以接受i - 1位置的预约，也可以不接受i - 1位置的预约。由于没有接受i位置的预约，所以此时的最长预约时长和选择完i - 1位置之后的最长预约时长相同，要么是接受i - 1位置的预约之后的最长预约时长f[i - 1]，要么是不接受i - 1位置的预约之后的最长预约时长g[i - 1]。所以不接受i位置的预约的最长预约时长是这两者的较大值，即g[i] = max(f[i - 1], g[i - 1])。

综上所述：f[i] = g[i - 1] + nums[i]，g[i] = max(f[i - 1], g[i - 1])。

初始化：根据状态转移方程，由于f[i]和g[i]都依赖于i - 1位置的值，所以我们要初始化f[0]和g[0]。

• f[0]表示接受0位置的预约之后，此时的最长预约时长，显然就是0位置的预约时长，即f[0] = nums[0]。
• g[0]表示不接受0位置的预约之后，此时的最长预约时长，显然g[0] = 0。

综上所述：f[0] = nums[0]，g[0] = 0。

填表顺序：根据状态转移方程，f[i]依赖于g[i - 1]，g[i]依赖于f[i - 1]和g[i - 1]，所以应从左往右填表，且同时填f表和g表。

返回值：假设有n个预约。题目要求我们返回，在选择完n - 1位置的预约之后，最长的预约时长。由于并不确定是否接受n - 1位置的预约，再根据状态表示，我们应返回f[n - 1]和g[n - 1]的较大值。

细节问题：f表和g表的规模和nums的规模相同，都是1 x n。另外，如果nums为空，直接返回0即可。

时间复杂度：O(N)，空间复杂度：O(N)。

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();// 处理边界情况if (n == 0) {return 0;}// 创建dp表vector<int> f(n);auto g = f;// 初始化f[0] = nums[0];// 填表for (int i = 1; i < n; i++) {for (int j = 1; j < n; j++) {f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}}return max(f[n - 1], g[n - 1]);}
};