来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/the-masseuse-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。
注意:本题相对原题稍作改动
示例 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。
二、题解
这道题目和198-打家劫舍几乎完全一样,思路也完全一样,代码都不用做太多更改。
思路:对于第i个用户,有2种策略选择,预约或不预约。
- 如果预约,那么说明上一个用户不能预约,只能取上上个用户的最优解加上当前用户的预约时长。
- 如果不预约,最优解就是上一个用户的最优解。
总结出来的状态转移(递推)方程:
\(dp[i] = max(dp[i-1], dp[i-2]+nums[i]])\)
三、代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int massage(vector<int> &nums) { int pprev, prev, output, i; output = prev = pprev = 0; if (nums.empty()) { return 0; } else if (nums.size() == 1) { return nums[0]; } prev = nums[0]; for (i = 1; i < nums.size(); i++) { output = max(prev, pprev + nums[i]); pprev = prev; prev = output; } return output; } }; |
单元测试:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
TEST(leetcode, demo) { Solution s; // leetcode样本数据 vector<int> v1{1, 2, 3, 1}, v2{2, 7, 9, 3, 1}, v3{2, 1, 4, 5, 3, 1, 1, 3}; // 特殊数据 vector<int> v4{1}, v5{1, 2}, v6; EXPECT_EQ(s.massage(v1), 4); EXPECT_EQ(s.massage(v2), 12); EXPECT_EQ(s.massage(v3), 12); // 1个元素的数组 EXPECT_EQ(s.massage(v4), 1); // 2个元素的数组 EXPECT_EQ(s.massage(v5), 2); // 空数组 EXPECT_EQ(s.massage(v6), 0); } |
头一回打败全部打败100%(其实是新题提交的人太少了):
评论