泰国金木棉做网站网站,温州网红打卡地,网站样版风格排版,wordpress接入公众号一个有名的按摩师会收到源源不断的预约请求#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列#xff0c;替按摩师找到最优的预约集合#xff08;总预约时间最长#xff09;#xff0c;…一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。
输入[1,2,3,1]输出4解释选择1号预约和3号预约总时长 1 3 4。输入[2,7,9,3,1],输出12解释选择1号预约、3号预约和5号预约总时长 2 9 1 12。输入[2,1,4,5,3,1,1,3]输出12解释选择1号预约、3号预约、5号预约和8号预约总时长 2 4 3 3 12。 这题是打家劫舍问题的变形。你个小偷换了个马甲我就不认识你了我们用动态规划的思想来解决这个问题。
确定状态表示根据经验和题目要求我们用dp[i]表示选择完i位置之后此时的最长预约时长。再细分为
用f[i]表示接受i位置的预约之后此时的最长预约时长。用g[i]表示不接受i位置的预约之后此时的最长预约时长。
推导状态转移方程
如果接受i位置的预约那么就不能接受i - 1位置的预约。所以接受i位置的预约之后的最长预约时长就等于不接受i - 1位置的预约之后的最长预约时长加上i位置的预约的时长即f[i] g[i - 1] nums[i]。如果不接受i位置的预约那么既可以接受i - 1位置的预约也可以不接受i - 1位置的预约。由于没有接受i位置的预约所以此时的最长预约时长和选择完i - 1位置之后的最长预约时长相同要么是接受i - 1位置的预约之后的最长预约时长f[i - 1]要么是不接受i - 1位置的预约之后的最长预约时长g[i - 1]。所以不接受i位置的预约的最长预约时长是这两者的较大值即g[i] max(f[i - 1], g[i - 1])。
综上所述f[i] g[i - 1] nums[i]g[i] max(f[i - 1], g[i - 1])。
初始化根据状态转移方程由于f[i]和g[i]都依赖于i - 1位置的值所以我们要初始化f[0]和g[0]。
f[0]表示接受0位置的预约之后此时的最长预约时长显然就是0位置的预约时长即f[0] nums[0]。g[0]表示不接受0位置的预约之后此时的最长预约时长显然g[0] 0。
综上所述f[0] nums[0]g[0] 0。
填表顺序根据状态转移方程f[i]依赖于g[i - 1]g[i]依赖于f[i - 1]和g[i - 1]所以应从左往右填表且同时填f表和g表。
返回值假设有n个预约。题目要求我们返回在选择完n - 1位置的预约之后最长的预约时长。由于并不确定是否接受n - 1位置的预约再根据状态表示我们应返回f[n - 1]和g[n - 1]的较大值。
细节问题f表和g表的规模和nums的规模相同都是1 x n。另外如果nums为空直接返回0即可。
时间复杂度O(N)空间复杂度O(N)。
class Solution {
public:int massage(vectorint nums) {int n nums.size();// 处理边界情况if (n 0) {return 0;}// 创建dp表vectorint f(n);auto g f;// 初始化f[0] nums[0];// 填表for (int i 1; i n; i) {for (int j 1; j n; j) {f[i] g[i - 1] nums[i];g[i] max(f[i - 1], g[i - 1]);}}return max(f[n - 1], g[n - 1]);}
};
