面试题 17.16. 按摩师 - 力扣LeetCode面试题 17.16. 按摩师 - 一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。注意本题相对原题稍作改动 示例 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。https://leetcode.cn/problems/the-masseuse-lcci/题目描述一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求数组代表每个预约的时长请计算按摩师在不接相邻预约的前提下可以接的最长总时长。等价题目打家劫舍不能选取相邻元素求选取元素最大和。思路分析动态规划核心划分状态。fx[i]第 i 个预约选择接时前 i 个预约最大总时长gx[i]第 i 个预约选择不接时前 i 个预约最大总时长如果接第 i 个预约i‑1 一定不能接只能取 i‑1 不接的结果再加上当前预约时长如果不接第 i 个预约i‑1 可以接也可以不接取两者最大值初始化i0第一个预约接第一个预约fx[0] nums[0]不接第一个预约gx[0] 0最后结果到最后一天接或者不接两者取最大值class Solution { public: int massage(vectorint nums) { int nnums.size(); if(n0) return 0; // fx表示该位置接,gx表示该位置不接 vectorintfx(n,0); vectorint gx(n,0); // 初始化 fx[0]nums[0]; gx[0]0; for(int i1;in;i) { fx[i]nums[i]gx[i-1]; gx[i]max(fx[i-1],gx[i-1]); } return max(fx[n-1],gx[n-1]); } };
