英文原文
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
中文题目
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 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。
通过代码
高赞题解
这道题其实就是经典的「力扣」第 198 题：打家劫舍。题目只问最优值，并没有问最优解，因此绝大多数情况下可以考虑使用「动态规划」的方法。
方法一：设计二维状态变量
第 1 步：设计状态
「状态」这个词可以理解为「记录了求解问题到了哪一个阶段」。
由于当前这一天有按摩师有两种选择：（1）接预约；（2）不接预约。但根据题意，今天是否接预约，是受到昨天影响的。为了消除这种影响，我们在状态数组要设置这个维度。
dp[i][0] 表示：区间 [0..i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长；dp[i][1] 表示：区间 [0..i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长。
说明：这个定义是有前缀性质的，即当前的状态值考虑了（或者说综合了）之前的相关的状态值，第 2 维保存了当前最优值的决策，这种通过增加维度，消除后效性的操作在「动态规划」问题里是非常常见的。
无后效性的理解：1、后面的决策不会影响到前面的决策； 2、之前的状态怎么来的并不重要。
一般的情况是，只要有约束，就可以增加一个维度消除这种约束带来的影响，再具体一点说，就是把「状态」定义得清楚、准确，「状态转移方程」就容易得到了。「力扣」的几道股票问题基本都是这个思路，而且设置状态的思想和这道题是完全一致的。
第 2 步：状态转移方程
「状态转移方程」可以理解为「不同阶段之间的联系」。
今天只和昨天的状态相关，依然是分类讨论：
- 今天不接受预约：或者是昨天不接受预约，或者是昨天接受了预约，取二者最大值，即：
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])； - 今天接受预约：只需要从昨天不接受预约转移而来，加上今天的时常，即：
dp[i][1] = dp[i - 1][0] + nums[i]。
第 3 步：考虑初始化
从第 2 天开始，每天的状态值只与前一天有关，因此第 1 天就只好老老实实算了。好在不难判断：dp[0][0] = 0 与 dp[0][1] = nums[0]；
这里有一种技巧，可以把状态数组多设置一行，这样可以减少对第 1 天的初始化，这样的代码把第 1 天的情况考虑了进去，但编码的时候要注意状态数组下标的设置， 请见题解最后的「参考代码 3」。
第 4 步：考虑输出
由于状态值的定义是前缀性质的，因此最后一天的状态值就考虑了之前所有的天数的情况。按摩师最后一天可以接受预约，也可以不接受预约，取二者最大值。
第 5 步：考虑是否可以优化空间
由于今天只参考昨天的值，可以使用「滚动数组」完成，优化空间以后的代码丢失了一定可读性，也会给编码增加一点点难度，请见题解后的「参考代码 4」。
参考代码 1：
[]public class Solution { public int massage(int[] nums) { int len = nums.length; if (len == 0) { return 0; } if (len == 1) { return nums[0]; } // dp[i][0]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长 // dp[i][1]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长 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(N)$，状态数组的大小为 $2N$，可以优化到常数级别，请见题解后的「参考代码 4」。
以上是中规中矩的写法。在这里根据问题本身的特点，状态可以不用设置那么具体，就将题目问的设计成状态，状态转移方程依然好写。
方法二：设计一维状态变量
第 1 步：定义状态
dp[i]：区间 [0，i] 里接受预约请求的最大时长。
第 2 步：状态转移方程
这个时候因为不限定下标为 i 这一天是否接受预约，因此需要分类讨论：
- 接受预约，那么昨天就一定休息，由于状态
dp[i - 1]的定义涵盖了下标为i - 1这一天接收预约的情况，状态只能从下标为i - 2的状态转移而来：dp[i - 2] + nums[i]； - 不接受预约，那么昨天可以休息，也可以不休息，状态从下标为
i - 1的状态转移而来：dp[i - 1]；
二者取最大值，因此状态转移方程为 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。
第 3 步：思考初始化
看状态转移方程，下标最小到 i - 2，因此初始化的时候要把 dp[0] 和 dp[1] 算出来，从 dp[2] 开始计算。
dp[0]：只有 1 天的时候，必须接受预约，因此dp[0] = nums[0]；dp[1]：头 2 天的时候，由于不能同时接受预约，因此最优值是这两天接受预约时长的最大值dp[1] = max(nums[0], nums[1])；
第 4 步：思考输出
由于定义的状态有前缀性质，并且对于下标为 i 的这一天也考虑了接受预约与不接受预约的情况，因此输出就是最后一天的状态值。
第 5 步：思考空间优化
看状态转移方程。当前状态只与前两个状态相关，我们只关心最后一天的状态值，因此依然可以使用「滚动变量」的技巧，这个时候滚动起来的就是 3 个变量了。这样的代码依然是丢失了可读性，也存在一定编码错误的风险，请见题解后的「参考代码 5」。
参考代码 2：
[]public class Solution { public int massage(int[] nums) { int len = nums.length; if (len == 0) { return 0; } if (len == 1) { return nums[0]; } // dp[i]：区间 [0, i] 里接受预约请求的最大时长 int[] dp = new int[len]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < len; i++) { // 今天在选与不选中，选择一个最优的 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[len - 1]; } }
复杂度分析：
- 时间复杂度：$O(N)$，$N$ 是数组的长度；
- 空间复杂度：$O(N)$，状态数组的大小为 $N$，可以优化到 $3$，请见题解后的「参考代码 5」。
我们看到解决这个问题的复杂程度与如何定义状态是相关的，定义状态的角度没有固定的模式，但有一个方向是可以考虑的，那就是从「状态转移方程」容易得到的角度去考虑如何设计状态。
「状态」和「状态转移方程」得到以后，这个问题其实就得到了解决，剩下的一些细节的问题在编码的时候只要稍微留意一点就行了。
总结
「动态规划」其实不是什么特别难懂的东西（只是说思想），只是这一类问题刚接触的时候有点不太适应，并且这类问题容易被包装得很过分，而且没有明显的套路，题型多样，所以学习「动态规划」会有一些些吃力，这没有办法，见多了就好。如果是准备面试，不需要掌握特别复杂的「动态规划」问题（当然前提是你没有在简历上说你是算法竞赛高手）。
「动态规划」告诉了我们另一种求解问题的思路。我们学习编程，习惯了自顶向下求解问题（递归），在自顶向下求解问题的过程中，发现了重复子问题，我们再加上缓存。而「动态规划」告诉我们，其实有一类问题我们可以从一个最简单的情况开始考虑，通过逐步递推，每一步都记住当前问题的答案，得到最终问题的答案，即「动态规划」告诉了我们「自底向上」思考问题的思路。
也就是说「动态规划」告诉我们的新的思路是：不是直接针对问题求解，由于我们找到了这个问题最开始的样子，因此后面在求解的过程中，每一步都可以参考之前的结果（在处理最优化问题的时候，叫「最优子结构」），由于之前的结果有重复计算（「重复子问题」），因此必须记录下来。
这种感觉不同于「记忆化递归」，「记忆化递归」是直接面对问题求解，遇到一个问题解决了以后，就记下来，随时可能面对新问题。而「动态规划」由于我们发现了这个问题「最初」的样子，因此每一步参考的以前的结果都是知道的，就像我们去考试，所有的考题我们都见过，并且已经计算出了答案一样，我们只需要参考以前做题的答案，就能得到这一题的答案，这是「状态转移」。应用「最优子结构」是同一回事，即：综合以前计算的结果，直接得到当前的最优值。
「动态规划」的内涵和外延很丰富，不是几句话和几个问题能够理解清楚的，需要我们做一些经典的问题去慢慢理解它，和掌握「动态规划」问题思考的方向。
参考代码 3：根据方法一：状态数组多设置一行，以避免对极端用例进行讨论。
[]public class Solution { public int massage(int[] nums) { int len = nums.length; // dp 数组多设置一行，相应地定义就要改变，遍历的一些细节也要相应改变 // dp[i][0]：区间 [0, i) 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长 // dp[i][1]：区间 [0, i) 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长 int[][] dp = new int[len + 1][2]; // 注意：外层循环从 1 到 =len，相对 dp 数组而言，引用到 nums 数组的时候就要 -1 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 - 1]; } return Math.max(dp[len][0], dp[len][1]); } }
复杂度分析：
- 时间复杂度：$O(N)$，$N$ 是数组的长度；
- 空间复杂度：$O(N)$，状态数组的大小为 $2(N + 1)$，记为 $O(N)$。
参考代码 4：根据方法一，使用「滚动数组」技巧，将空间优化到常数级别
在编码的时候，需要注意，只要访问到 dp 数组的时候，需要对下标 % 2，等价的写法是 & 1。
[]public class Solution { public int massage(int[] nums) { int len = nums.length; if (len == 0) { return 0; } if (len == 1) { return nums[0]; } // dp[i & 1][0]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长 // dp[i & 1][1]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长 int[][] dp = new int[2][2]; dp[0][0] = 0; dp[0][1] = nums[0]; for (int i = 1; i < len; i++) { dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1]); dp[i & 1][1] = dp[(i - 1) & 1][0] + nums[i]; } return Math.max(dp[(len - 1) & 1][0], dp[(len - 1) & 1][1]); } }
复杂度分析：
- 时间复杂度：$O(N)$，$N$ 是数组的长度；
- 空间复杂度：$O(1)$，状态数组的大小为 $4$，常数空间。
参考代码 5：根据方法二，使用 3 个变量滚动完成计算，将空间优化到常数级别。
在实现上可以在取下标的时候对 3 取模。
[]class Solution { public int massage(int[] nums) { int len = nums.length; if (len == 0) { return 0; } if (len == 1) { return nums[0]; } // dp[i % 3]：区间 [0，i] 里接受预约请求的最大时长 int[] dp = new int[3]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < len; i++) { // 今天在选与不选中，选择一个最优的 dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + nums[i]); } return dp[(len - 1) % 3]; } }
复杂度分析：
- 时间复杂度：$O(N)$，$N$ 是数组的长度；
- 空间复杂度：$O(1)$，状态数组的大小为 $3$，常数空间。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 62474 | 120777 | 51.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
