一個(gè)有名的按摩師會(huì)收到源源不斷的預(yù)約請求，每個(gè)預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時(shí)間，因此她不能接受相鄰的預(yù)約。給定一個(gè)預(yù)約請求序列，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時(shí)間最長），返回總的分鐘數(shù)。

注意：本題相對原題稍作改動(dòng)

示例 1：

輸入： [1,2,3,1]
輸出： 4
解釋： 選擇 1 號預(yù)約和 3 號預(yù)約，總時(shí)長 = 1 + 3 = 4。
示例 2：

輸入： [2,7,9,3,1]
輸出： 12
解釋： 選擇 1 號預(yù)約、 3 號預(yù)約和 5 號預(yù)約，總時(shí)長 = 2 + 9 + 1 = 12。
示例 3：

輸入： [2,1,4,5,3,1,1,3]
輸出： 12
解釋： 選擇 1 號預(yù)約、 3 號預(yù)約、 5 號預(yù)約和 8 號預(yù)約，總時(shí)長 = 2 + 4 + 3 + 3 = 12。

來源：力扣（LeetCode）

C++1 動(dòng)態(tài)規(guī)劃

1、當(dāng)預(yù)約請求長度為0時(shí)，返回0
2、當(dāng)預(yù)約長度為1時(shí)，就選擇這一天
3、使用一維數(shù)組記錄當(dāng)天的最長預(yù)約，如果選擇接第i個(gè)預(yù)約，則前一天不能接預(yù)約請求，需要從第i-2個(gè)預(yù)約轉(zhuǎn)移過來；如果不接第
i個(gè)預(yù)約請求，第i-1個(gè)預(yù)約接還是不接都可以，則可以從第i-1個(gè)請求轉(zhuǎn)移過來。取兩種選擇的最大值即可。

此方法采用自底向上的動(dòng)態(tài)規(guī)劃，遞推方程：
res_dp[i] = max(res_dp[i - 1], res_dp[i - 2] + nums[i])

class Solution {
public:
    int massage(vector<int>& nums) {
        int s = nums.size();
        if(s == 0){
            return 0;
        }
        if(s == 1){
            return nums[0];
        }
        vector<int> res_dp(s,0);
        res_dp[0] = nums[0];
        res_dp[1] = max(nums[0],nums[1]);
        for(int i=2;i<s;i++){
            res_dp[i] = max(res_dp[i-1], res_dp[i-2]+nums[i]);
        }
        return res_dp[s-1];
    }
};