力扣加加题解1883. 准时抵达会议现场的最小跳过休息次数——动态规划与浮点精度攻防实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本题LeetCode 1883 / 力扣 5775考察的是在逐路行驶 整数时刻等待这一特殊时间模型下如何通过最少次数的跳过休息操作准时抵达会议现场。本文以 problems/5775.minimum-skips-to-arrive-at-meeting-on-time.md 为骨架完整还原题目模型、动态规划推导、边界处理与浮点精度陷阱并结合本仓库的 动态规划专题 与 二分查找专题 深入剖析为什么这道题不能二分、必须 DP读完你不仅能拿下本题还能掌握一套带取整操作 浮点精度类 DP 的通用处理范式。题目描述与时间模型建模给定dist[i]第i条道路的长度单位千米共n条道路speed行驶速度单位千米/小时hoursBefore距离开会剩余的可用小时数。行驶规则如下通过第i条路花费时间为dist[i] / speed小时通过第i条路之后必须休息并等待直到下一个整数小时才能继续通过下一条路最后一条路通过后不需要休息因为已经抵达会场你可以跳过某些道路之后的休息即不等待到下一个整数小时立即进入下一条路。示例说明来自原题描述若通过一条路用去1.4小时则必须等待到2小时才能继续若恰好用去2小时则无需等待。假设通过第 1 条路用去1.4小时、第 2 条路用去0.6小时若跳过第 1 条路后的休息你会在恰好2小时完成第 2 条路并可立即开始第 3 条路。要求返回准时抵达会议现场所需的最小跳过次数若无论如何都无法准时参会返回-1。输入输出示例输入输出解释dist [1,3,2],speed 4,hoursBefore 21不跳过休息需2.5小时跳过第 1 次休息后需1.5小时dist [7,3,5,5],speed 2,hoursBefore 102跳过第 1、3 次休息恰好10小时抵达dist [7,3,5,5],speed 1,hoursBefore 10-1即使跳过所有休息也无法准时参会数据范围n dist.length 1 n 1000 1 dist[i] 10^5 1 speed 10^6 1 hoursBefore 10^7数据规模决定了算法上界n最大 1000暗示O(n^2)级别的动态规划是可行方向而dist[i]与speed的跨度决定了过程中必然出现非整数耗时为后面的浮点精度问题埋下伏笔。思路推演为什么能力检测二分行不通拿到最小跳过次数这类最值问题第一直觉往往是能力检测二分又称可行性二分——即二分答案k检查跳过k次休息是否可行。原文档作者明确否定了这一思路理由非常关键possible(rest_count)实现起来复杂度太高。因为rest_count的分布情况是不确定的。令 dist 长度为 nrest_count为 r那么分布情况就有 $C_{n}^{r}$ 种。这种枚举显然是不合适的。也就是说可行性判定本身需要穷举哪 r 条路后面跳过休息的所有组合而组合数 $C_n^r$ 在n 1000时是天文数字。二分的 $O(\log n)$ 层数救不了内部指数级的判定成本因此二分路线整体不可行。对能力检测二分范式感兴趣的读者可对照本仓库的 二分查找专题内含模板与典型应用体会其适用前提可行性判定必须是多项式时间否则二分只会放大开销。排除二分之后自然转向动态规划——把分布情况这一不确定因素收敛进状态维度正是 DP 的强项。动态规划解法状态定义与转移方程状态定义令dp[i][j]表示到达dist[i-1]即第 i 条路的终点且已经休息了 j 次第 j 次休息完毕所需要的时间。第一维i从 1 到n对应逐条道路推进天然构成 DP 的阶段第二维j0 j i记录已使用的跳过/休息次数。这与仓库 动态规划专题 反复强调的核心方法论完全一致状态定义是动态规划的灵魂。本题之所以把休息次数纳入状态正是因为它既影响后续时刻的整数对齐关系进而影响总耗时又正是题目所求的答案维度——休息次数既是约束又是目标一举两得。转移方程对第i条路长度为cur dist[i-1]有两种选择第 j 次休息不跳过等待到整数小时dp[i][j] dp[i-1][j] ceil(cur / s)即先到达第 i-1 条路终点此时已休息 j 次走完第 i 条路后向上取整到下一个整数小时。第 j 次不休息跳过等待直接进入下一条路dp[i][j] dp[i-1][j-1] cur即到达第 i-1 条路终点时只休息了 j-1 次本次选择跳过直接累加真实行驶时间cur注意这里cur需要与dp保持同一量纲见下文精度处理。两者取最小值dp[i][j] min(休息方案, 不休息方案)。边界条件dp[0][0] 0起点状态未出发、未休息耗时 0j从 0 枚举到i休息次数不可能超过已走过的道路数j 0时不能选择不休息因为每次不休息都意味着在某个路口跳过了休息而跳过休息本身就是一次计数若 j 为 0则前 i 条路之后都不能有跳过行为第 i 条路之后的等待必须发生除非是最后一条路因此dp[i][0]只能由休息分支转移而来。这正是原文档强调的j 0 不能选择不休息因为这不符合题意。答案的提取由于题目要求最小的休息次数从小到大枚举j一旦出现dp[n][j] hoursBefore即说明 j 次休息已足够准时直接返回该j。若全部枚举完毕仍不满足返回-1。浮点精度陷阱0.3333…的累积灾难原文档给出了一个非常典型的反例0.33333xxx33 0.33333xx33 0.3333xx33 1.0000000000xx002三个 1/3 的真实和是1但在 IEEE 754 浮点数下计算出的结果会略大于1。本题的休息 向上取整操作会把这种误差放大为错误真实时间恰好是整数小时本可以直接继续无需等待但浮点累积后得到1.0000000000xx002向上取整变成2导致多计了近乎 1 个小时原本可以准时到达的方案被误判为超时答案就可能偏大甚至返回-1。两种常见解法化小数为整数原文档采用把时间全部乘以speed让所有运算在整数域进行从根本上消灭浮点误差设置精度阈值若两个数之差小于某个精度值如1e-9则视为相等配合取整前做微小修正。整数化的具体实现关键技巧原文档点明(cur s - 1) // s ≡ math.ceil(cur / s)即向上取整可以用整数运算(cur s - 1) // s精确实现//为整除、/为实数除法。将dp[i][j]整体乘以s之后休息分支dp[i][j] (dp[i-1][j] cur s - 1) // s * s—— 先做整数域的向上取整对齐再乘回s保持量纲一致此时cur也乘以了s不休息分支dp[i][j] min(dp[i][j], dp[i-1][j-1] cur)—— 直接累加不取整可行性判定dp[n][j] hoursBefore * s比较双方都在整数域进行判定结果精确无歧义。由于题目求最小值dp数组可全部初始化为一个足够大的值原文档给出的方案是s * h 1任何合法状态都不可能超过该值的上界数学上等价于无穷大。完整代码Python3class Solution: def minSkips(self, dists: List[int], s: int, h: int) - int: n len(dists) dp [[s * h 1] * (n 1) for i in range(n 1)] dp[0][0] 0 for i in range(1, n 1): cur dists[i - 1] for j in range(i 1): # rest向上取整到下一个整数小时整数化后等价于 math.ceil dp[i][j] (dp[i - 1][j] cur s - 1) // s * s # no rest跳过本次休息直接累加真实耗时 if j 0: dp[i][j] min(dp[i][j], dp[i - 1][j - 1] cur) # 提前返回j 从小到大枚举首次满足即为最小跳过次数 if dp[-1][j] h * s: return j return -1逐行要点dp [[s * h 1] * (n 1) for i in range(n 1)]二维表初始化s * h 1充当无穷大内层j从 0 到i严格限制j i保证状态合法dp[i][j] (dp[i-1][j] cur s - 1) // s * s恒先执行保证j 0时只有休息分支可用if dp[-1][j] h * s: return j在内层循环中同步判断一旦发现当前j已能让最后一条路dp[-1]即dp[n]准时抵达立即返回——这正是最小跳过次数的贪心式提取无需等整张表算完。复杂度分析令n为数组长度时间复杂度O(n^2)—— 双层循环外层遍历 n 条路内层枚举 0..i 共n(n1)/2个状态空间复杂度O(n^2)—— 二维dp表可进一步优化为滚动数组压到O(n)感兴趣的读者可自行尝试注意j的逆序枚举以保证转移依赖的dp[i-1][j-1]未被覆盖。复杂度与仓库 动态规划专题 中DP 的时间空间复杂度打底就是状态总数参数取值范围的笛卡尔积的论断完全吻合本题状态数为n * n量级故复杂度为O(n^2)。关键点总结识别范式带跳过/不跳过二元决策 最少次数求值 → 动态规划先排除可行性二分因为组合分布 $C_n^r$ 使判定不可行状态定义dp[i][j] 到达第 i 条路终点且已休息 j 次所需时间把不确定的分布收敛为第二个状态维度转移二元性休息分支做向上取整(cur s - 1) // s * s不休息分支直接累加两者取min边界纪律dp[0][0] 0j从 0 到ij 0禁止不休息分支浮点精度把全部时间乘以speed化小数为整数用整数取整代替math.ceil彻底规避0.333…累加产生的1.0000000…2型误差提前返回从小到大枚举j首次满足dp[n][j] hoursBefore即返回保证答案最小。延伸阅读本题完整题解problems/5775.minimum-skips-to-arrive-at-meeting-on-time.md动态规划方法论状态定义、转移方程、枚举状态三件套thinkings/dynamic-programming.md能力检测二分范式与模板91/binary-search.md更多取整/精度类题目可对照 problems/875.koko-eating-bananas.md同样使用(pile mid - 1) // mid的整数取整技巧【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考