深圳网站建设服务中心,湖南网站建设公司 要上磐石网络,手表官方网站,内蒙古做网站公司1. 题目
一个有名的理发师会收到源源不断的预约请求#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列#xff0c;替理发师找到最优的预约集合#xff08;总预约时间最长#xff09;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替理发师找到最优的预约集合总预约时间最长返回总的分钟数。
注意本题相对原题稍作改动
示例 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。来源力扣LeetCode 链接https://leetcode-cn.com/problems/the-masseuse-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
dp[i] 表示第 i 次预约的 最长时间第 i 次预约那么可以 dp[i-2]第 i 次不预约可以直接取 dp[i-1]所以转态转移方程dp[i]max(dp[i−2]nums[i],dp[i−1])dp[i] \max(dp[i-2]nums[i], dp[i-1])dp[i]max(dp[i−2]nums[i],dp[i−1])
类似题目 LeetCode 198. 打家劫舍DP LeetCode 213. 打家劫舍 IIDP LeetCode 337. 打家劫舍 III记忆化递归
class Solution {
public:int massage(vectorint nums) {int i, n nums.size();if(n 0) return 0;if(n 1) return nums[0];int dp[n] {0};dp[0] nums[0];dp[1] max(nums[0],nums[1]);for(i 2; i n; i){dp[i] max(dp[i-2]nums[i], dp[i-1]);}return dp[n-1];}
};
