当前位置: 首页> 游戏> 手游 > 菏泽网站建设制作_web手机编程软件_爱站网官网查询域名_百度收录入口提交查询

菏泽网站建设制作_web手机编程软件_爱站网官网查询域名_百度收录入口提交查询

时间:2025/7/12 3:18:11来源:https://blog.csdn.net/shuibuxingaaa/article/details/147169834 浏览次数:0次
菏泽网站建设制作_web手机编程软件_爱站网官网查询域名_百度收录入口提交查询

动态规划解决按摩师预约问题——以LeetCode面试题17.16为例

1.题目链接

LeetCode面试题17.16 按摩师

2.题目描述

一个有名的按摩师收到一系列的预约请求,每个预约都可以选择接受或不接受。但相邻的预约不能同时接受。给定一个包含各预约时长的数组 nums,求她能获得的最长总时间。若数组为空,返回0。

3.示例分析

示例1:
输入:[1,2,3,1]
输出:4
解释:接受第1个(时长1)和第3个(时长3)预约,总时长为1+3=4;或接受第2个(2)和第4个(1),总时长为3。因此最大值为4。

示例2:
输入:[2,7,9,3,1]
输出:12
解释:选择第1、3、5个预约,总时长2+9+1=12。

4.算法思路

动态规划状态定义:

  • f[i] 表示接受第 i 个预约时的最大总时长。
  • g[i] 表示不接受第 i 个预约时的最大总时长。

状态转移方程:

  1. 若接受第 i 个预约,则第 i-1 个必须未被接受:
    f[i] = g[i-1] + nums[i]
  2. 若不接受第 i 个预约,则第 i-1 个可接受或不接受:
    g[i] = max(f[i-1], g[i-1])

最终结果:
fg 数组最后一个元素的最大值,即 max(f[n-1], g[n-1])

5.边界条件与注意事项

  1. 空数组处理: 直接返回0。
  2. 单元素数组: 直接返回该元素值。
  3. 数组索引范围: 遍历时需从第2个元素(索引1)开始。
  4. 状态初始化: f[0] = nums[0](选第一个),g[0] = 0(不选第一个)。

6.代码实现

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if(n == 0) return 0; // 空数组直接返回0vector<int> f(n), 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]); // 最终取最大值}
};

代码解析:

  • 时间复杂度: O(n),遍历数组一次。
  • 空间复杂度: O(n),使用两个数组存储状态;可优化为O(1)(用变量替代数组)。
  • 关键点: 通过动态规划维护两个状态,确保每一步的选择满足不相邻条件,最终得到全局最优解。
关键字:菏泽网站建设制作_web手机编程软件_爱站网官网查询域名_百度收录入口提交查询

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: