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

第 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 天的情况考虑了进去，但编码的时候要注意状态数组下标的设置。

第 4 步：考虑输出
由于状态值的定义是前缀性质的，因此最后一天的状态值就考虑了之前所有的天数的情况。按摩师最后一天可以接受预约，也可以不接受预约，取二者最大值。

第 5 步：考虑是否可以状态压缩
由于今天只参考昨天的值，状态可以压缩，可以使用「滚动数组」完成，状态压缩的代码丢失了一定可读性，也会给编码增加一点点难度。

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]);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // int[] nums = {1, 2, 3, 1};
        // int[] nums = {2, 7, 9, 3, 1};
        int[] nums = {2, 1, 4, 5, 3, 1, 1, 3};
        int res = solution.massage(nums);
        System.out.println(res);
    }
}