題目

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/the-masseuse-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

C++實現(xiàn)

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