准时抵达会议现场的最小跳过休息次数

难度: Hard

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。

当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。

例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。

然而，为了能准时到达，你可以选择跳过一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。

例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。

返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。

示例 1：

输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。

示例 2：

输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。

示例 3：

输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。

提示：

n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 10⁵
1 <= speed <= 10⁶
1 <= hoursBefore <= 10⁷

Submission

运行时间: 1066 ms

内存: 16.2 MB

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        target = hoursBefore * speed
        n = len(dist)
        dp = [0] * (n + 1)
        for i in range(n):
            new = [float('inf')] * (n + 1)
            for j in range(i + 2):
                new[j] = min((dp[j - 1] if j > 0 else float('inf')) + dist[i], ((dp[j] + dist[i] - 1) // speed + 1) * speed)
            dp = new 
        for i in range(n + 1):
            if dp[i] <= target:
                return i 
        return - 1

Explain

此题考虑使用动态规划解决。定义dp[j]表示在跳过前j次休息的条件下，经过当前所有道路所需的最少时间（调整至下一个整点开始）。在迭代每一条道路的过程中，我们需要更新dp数组，以包括两种情况：(1) 跳过这条道路的休息时间，即直接加上这条道路的行驶时间；(2) 不跳过这条道路的休息时间，即将当前总时间调整到下一个整点小时，再加上这条道路的行驶时间。我们为每一种情况都计算可能的时间，并更新dp数组。最后，检查dp数组中最小的j值，使得dp[j]不超过hoursBefore * speed，即可到达会议现场的时间限制。如果所有j都无法满足条件，则返回-1。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        target = hoursBefore * speed  # 转换总时间限制为距离
        n = len(dist)
        dp = [0] * (n + 1)  # 初始化dp数组，dp[j]表示跳过j次休息后的最小时间
        for i in range(n):  # 遍历每条道路
            new = [float('inf')] * (n + 1)  # 初始化新的dp数组
            for j in range(i + 2):  # 遍历每种跳过休息的情况
                if j > 0:
                    new[j] = min(new[j], (dp[j - 1] if j > 0 else float('inf')) + dist[i])  # 跳过这条道路的休息时间
                new[j] = min(new[j], ((dp[j] + dist[i] - 1) // speed + 1) * speed)  # 不跳过休息，等到下一个整点小时
            dp = new  # 更新dp数组
        for i in range(n + 1):  # 检查最小的跳过次数
            if dp[i] <= target:
                return i  # 如果满足时间限制，则返回跳过的次数
        return -1  # 如果所有情况都不满足，返回-1

Explore

动态规划的状态转移方程是通过分析每一条道路的行进和休息情况来定义的。定义 dp[j] 为跳过前 j 次休息后，经过当前所有道路所需的最少时间。更新 dp 数组时，考虑两种情况：1) 跳过这条道路的休息时间，直接加上这条道路的行驶时间；2) 不跳过这条道路的休息时间，将当前总时间调整到下一个整点小时后，再加上这条道路的行驶时间。这两种情况确保我们能够根据不同的时间管理策略（即是否跳过休息），找到到达会议现场的最佳路径。

这个表达式用于将当前总时间调整到下一个整点小时。具体来说，`(dp[j] + dist[i] - 1)` 为通过当前道路后的总时间（减1是为了处理整除的边界条件）。整除 `speed` 后加1，将时间向上舍入到下一个整数，这代表需要等待到下一个整点小时开始。最后，乘以 `speed` 将单位从小时转换回距离单位。这样确保了在不跳过休息的情况下，每次行驶结束都能在整点时刻出发，这是休息策略的模拟。

是的，这个逻辑能保证在所有的跳过休息的情况下找到最优解。dp 数组记录了从0次到最多可能的跳过次数的每种情况下的最小时间。通过检查每个 dp[j] 是否小于等于 `hoursBefore * speed`，可以确保我们找到的解是在允许的时间内到达目的地的最少跳过次数。如果所有的 dp[j] 都超过了限制，返回 -1 表示无法在规定时间内到达。