南安市网站建设,百度快照如何优化,梅林 建站 wordpress,陕西住房与城乡建设部网站个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。
示例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。 2️⃣题目解析
dp[i]表示i位置为当前的最长按摩时间。根据题目要求由于第i个位置我们可以选择也可以不选择所以我们需要对dp[i]表的这两种状态进行细分
第一种状态选择i位置用vectorint f(n)来表示该状态。 第二种状态不选择i位置用vectorint g(n)来表示该状态。
关于初始化的话如下
f[0] nums[0]第一次预约选择即f[0]的值当然是第一次预约时间啦g[0] 0第一次预约不选择的话表示0位置的值就是0啦
状态转移方程如下
f[i] g[i-1] nums[i]g[i] (f[i-1] , g[i-1])
返回值max(f[n-1],g[n-1])
3️⃣解题代码
class Solution {
public:int massage(vectorint nums) {int n nums.size();if(n 0) return 0;// 创建dp表vectorint f(n);vectorint g(n);// 初始化f[0] nums[0],g[0] 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]);}
};代码通过
