网站建设平台,免费创建自己的网站,青岛建设公司网站费用,做网站要求什么力扣原题链接#xff0c;点击跳转。
一个有名的按摩师会收到源源不断的预约请求#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列nums#xff0c;总共有n个预约#xff0c;替按摩师找到…力扣原题链接点击跳转。
一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列nums总共有n个预约替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。
我们用动态规划的思想解决这个问题。首先创建dp表确定状态表示很自然地想到可以用dp[i]表示一直收到下标为i的请求后接受的预约的最长总时长。然而这么想是不够的因为对于每个预约都有可能接受或者不接受。所以要分类讨论用f[i]表示接受下标为i的请求后接受的预约的最长总时长用g[i]表示不接受下标为i的请求后接受的预约的最长总时长。
接着推导状态转移方程。对于f[i]接受了下标为i的预约说明没有接受下标为i-1的预约此时接受的预约的最长总时长应为g[i-1]nums[i]。对于g[i]不接受下标为i的预约有可能接受了下标为i-1的预约也有可能不接受下标为i-1的预约由于要求最长总时长所以g[i]max(f[i-1],g[i-1])。
初始化时只需把f[0]初始化成nums[0]g[0]初始化成0再从左往右同时填f表和g表。最后返回max(f[n-1],g[n-1])。
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){f[i] g[i - 1] nums[i];g[i] max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};
