题目描述

给你一个整数 hoursBefore，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 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 = 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 条道路。

输入：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 小时
抵达会议现场。

输入：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

算法

(动态规划) $O(n^2)$

1. 设状态 $f(i, j)$ 表示通过了 $i$ 条路，使用了 $j$ 次跳过休息时所需要的最少时间。其中 $i$ 的范围是 $[1, n]$。
2. 初始时，$f(0, 0) = 0$，其余为正无穷。
3. 转移时，对于当前 $f(i, j)$ 有两种决策
   • 第 $i$ 条路不使用跳过，$f(i, j) = \min(f(i, j), \lceil f(i - 1, j) + \frac{dist(i)}{speed}\rceil)$。
   • 另一种是在符合要求的条件下使用跳过，转移 $f(i, j) = \min(f(i, j), f(i - 1, j - 1) + \frac{dist(i)}{speed})$。
4. 最终答案为 $f(n, j) \le hoursBefore$ 时最小的 $j$。
5. 注意，如果使用 double 存储浮点数，则可能会出现精度问题，在上取整前，先减去一个小量避免精度误差被放大。当然，也可以选择使用分数存储。

时间复杂度

• 状态数为 $O(n^2)$，每次转移只需要常数时间，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储状态。

C++ 代码

const double eps = 1e-8;

class Solution {
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        const int n = dist.size();
        const double INF = 1e20;

        vector<vector<double>> f(n + 1, vector<double>(n + 1, INF));
        f[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                f[i][j] = min(f[i][j], 
                    ceil(f[i - 1][j] + 1.0 * dist[i - 1] / speed - eps));

                if (j > 0 && i < n)
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1.0 * dist[i - 1] / speed);
            }
        }

        for (int j = 0; j < n; j++)
            if (f[n][j] - eps <= hoursBefore)
                return j;

        return -1;
    }
};