LeetCode - 面试题 17.16. 按摩师

面试题 17.16. 按摩师

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

注意：本题相对原题稍作改动

解题思路： 看到这种「某个元素可选或不选的二值状态」的题，一开始想到的是01背包问题，但是此题不用考虑的那么复杂，不过思路是对的，本题需要用动态规划解题。

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