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

给你一个整数 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] <= 105
• 1 <= speed <= 106
• 1 <= hoursBefore <= 107

方法一：动态规划

思路与算法

我们用 f[i][j] 表示经过了 dist}[0] 到 dist}[i-1] 的 i 段道路，并且跳过了 j 次的最短用时。

在进行状态转移时，我们考虑最后一段道路 dist}[i-1] 是否选择跳过：

• 如果没有跳过，那么状态转移方程为：

  f[i][j] = \left\lceil f[i-1][j] + \textit{dist}[i-1]}{\textit{speed} } \right\rceil

  其中 \lceil x \rceil 表示将 x 向上取整。对于最后一段道路，我们无需等待到下一个整数小时，但由于题目中给定的 hoursBefore 是一个整数，因此在状态转移方程中向上取整是不会影响结果的。

• 如果跳过，那么状态转移方程为：

  f[i][j] = f[i-1][j-1] + \textit{dist}[i-1]}{\textit{speed} }

由于我们到达的时间尽可能早，因此需要选择这两种转移中的较小值，即：

f[i][j] = \min \left{ \left\lceil f[i-1][j] + \textit{dist}[i-1]}{\textit{speed} } \right\rceil, f[i-1][j-1] + \textit{dist}[i-1]}{\textit{speed} }\right}

需要注意的是，当 j=0 时，我们不能通过「跳过」进行转移；当 j=i 时，我们不能通过「没有跳过」进行转移；当 j>i 时，我们无法在 i 段道路内跳过超过 i 次，对应的状态不合法。

当我们计算完所有状态的值后，我们只需要找到最小的 j，使得 f[n][j] \leq \textit{hoursBefore，这个 j 即为最少需要跳过的次数。如果不存在这样的 j，那么返回 -1。

动态规划的细节

动态规划的边界条件为 f[0][0] = 0，表示初始（未走过任何道路）时的时间为 0。

由于状态转移方程中的取值为 \min，因此我们可以将除了 f[0][0] 以外所有的状态置为一个极大值 \infty，方便进行转移。

浮点数运算的细节

这一部分非常重要，希望读者仔细阅读。

根据 IEEE 754 标准 ，浮点数在计算机中存储的精度是有限的，而本题中我们不可避免的会使用「浮点数运算」以及「向上取整」运算，如果强行忽略产生的计算误差，会得到错误的结果。

举一个简单的例子，假设使用的语言中「向上取整」运算的函数为 ceil，下面的运算：

\texttt{ceil(8.0 + 1.0 / 3 + 1.0 / 3 + 1.0 / 3)}

应当是 9，而计算机会给出 10。这是因为浮点数误差导致：

\texttt{8.0 + 1.0 / 3 + 1.0 / 3 + 1.0 / 3}

计算出的结果约为：

\texttt{9.000000000000002}

向上取整后会得到 10，产生了错误的答案。

因此我们引入常量 eps 表示一个极小值，例如 10^{-8。在进行「向上取整」运算前，我们将待取整的浮点数减去 eps 再进行取整，就可以避免上述的误差。

同时，我们需要说明 eps 不会引入其它的问题。在本题中速度最大为 10^6，时间与速度成反比，那么 eps 的粒度只需要高于时间的精度 10^{-6 即可，取 10^{-7 或 10^{-8 都是可行的。

最后在比较 f[n][j] \leq \textit{hoursBefore 时，我们也需要将左侧减去 eps 或将右侧加上 eps，再进行比较。

代码

[sol1-C++]

class Solution {
private:
    // 可忽略误差
    static constexpr double EPS = 1e-7;
    // 极大值
    static constexpr double INFTY = 1e20;

public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<vector<double>> f(n + 1, vector<double>(n + 1, INFTY));
        f[0][0] = 0.;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j != i) {
                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + (double)dist[i - 1] / speed - EPS));
                }
                if (j != 0) {
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + (double)dist[i - 1] / speed);
                }
            }
        }
        for (int j = 0; j <= n; ++j) {
            if (f[n][j] < hoursBefore + EPS) {
                return j;
            }
        }
        return -1;
    }
};

[sol1-Python3]

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        # 可忽略误差
        EPS = 1e-7
        
        n = len(dist)
        f = [[float("inf")] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 0.
        for i in range(1, n + 1):
            for j in range(i + 1):
                if j != i:
                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] / speed - EPS))
                if j != 0:
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] / speed)
        
        for j in range(n + 1):
            if f[n][j] < hoursBefore + EPS:
                return j
        return -1

复杂度分析

• 时间复杂度：O(n^2)。

• 空间复杂度：O(n^2)，即为存储所有状态需要的空间。

方法二：动态规划 + 将所有运算变为整数运算

思路与算法

我们可以将数组 dist 中的道路长度和 hoursBefore 都乘以 speed。由于方法一的代码中所有除法运算的除数都是 speed，因此这样做可以保证所有的除法运算的结果都是整数，从根本上避免浮点数误差。

但需要注意的是，在题目中我们规定「必须休息并等待，直到下一个整数小时才能开始继续通过下一条道路」，那么当我们将上面的变量都乘以 speed 后，规定应当变更为「必须休息并等待，直到下一个 speed 的倍数小时才能开始继续通过下一条道路」。

其余的逻辑与方法一完全相同，读者可以比较方法一和方法二的代码体会其中的差异。

细节

时间 x 的下一个 speed 的倍数小时为：

\left( \lfloor x-1}{\textit{speed} } \rfloor + 1 \right) \cdot \textit{speed}

其中 \lfloor x \rfloor 表示将 x 向下取整。

代码

[sol2-C++]

class Solution {
private:
    using LL = long long;

public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<vector<LL>> f(n + 1, vector<LL>(n + 1, LLONG_MAX / 2));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j != i) {
                    f[i][j] = min(f[i][j], ((f[i - 1][j] + dist[i - 1] - 1) / speed + 1) * speed);
                }
                if (j != 0) {
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1]);
                }
            }
        }
        for (int j = 0; j <= n; ++j) {
            if (f[n][j] <= (LL)hoursBefore * speed) {
                return j;
            }
        }
        return -1;
    }
};

[sol2-Python3]

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        f = [[float("inf")] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(i + 1):
                if j != i:
                    f[i][j] = min(f[i][j], ((f[i - 1][j] + dist[i - 1] - 1) // speed + 1) * speed)
                if j != 0:
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1])
        
        for j in range(n + 1):
            if f[n][j] <= hoursBefore * speed:
                return j
        return -1

复杂度分析

• 时间复杂度：O(n^2)。

• 空间复杂度：O(n^2)，即为存储所有状态需要的空间。