Loading... > https://leetcode.cn/problems/minimum-skips-to-arrive-at-meeting-on-time/description/?envType=daily-question&envId=2024-04-11 ### DP 通过 $n$ 条路跳过休息次数最少，显然最优解中通过 $n - 1$ 条路的跳过次数也是最少的。走过的路对后面路的选择显然没有影响，因此考虑使用 DP 求解。 令 $T[i][j]$ 为在跳过了 $j$ 次休息后走完 $i$ 条路所花费的时间，有如下两种情况： $$ \begin{equation} T[i][j]= \begin{cases} \lceil T[i - 1][j] + dist[i - 1] / speed \rceil &\mbox{if not skip} \\ T[i - 1][j - 1] + dist[i - 1] / speed &\mbox{if skip} \end{cases} \end{equation} $$ 其中 $\lceil x \rceil$ 为对 $x$ 向上取整。 题目要求要在规定时间内到达，所以 $T[i][j]$ 需要尽可能小，可以写出递推公式如下： $$ T[i][j] = min \{ \lceil T[i - 1][j] + dist[i - 1] / speed \rceil, T[i - 1][j - 1] + dist[i - 1] / speed \} $$ 其中有几个注意点： - $j = 0$ 的时候不能进行跳过。第 $i$ 步都没有跳过第 $i - 1$ 步肯定没有跳过。 - $j = i$ 的时候必须进行跳过。前面每一步都进行跳过的情况下 $j$ 才可能等于 $i$ 。 - $j > i$ 的情况不存在。每段路程最多进行一次跳过，所以 $j$ 不可能大于 $i$ 。 这里有个坑，根据 IEEE 754 标准，浮点数在计算机中存储的精度是有限的，而本题中我们不可避免的会使用「浮点数运算」以及「向上取整」运算，如果强行忽略产生的计算误差，会得到错误的结果。 举一个简单的例子，假设使用的语言中「向上取整」运算的函数为 $ceil$，下面的运算： $$ ceil(8.0 + 1.0 / 3 + 1.0 / 3 + 1.0 / 3) $$ 结果应当是 $9$ ，而计算机会给出 $10$ 。这是因为浮点数误差导致： $8.0 + 1.0 / 3 + 1.0 / 3 + 1.0 / 3$ 计算出的结果约为：$9.000000000000002$ ，向上取整后会得到 $10$ ，产生了错误的答案。 因此需要引入常量 $eps$ 表示一个极小值，例如 $10^{-8}$ 。在进行「向上取整」运算前，将待取整的浮点数减去 $eps$ 再进行取整，就可以避免上述的误差。 ```c++ class Solution { public: int minSkips(std::vector<int>& dist, int speed, int hoursBefore) { const double EPS = 1e-8, INF = 1e18; const int n = dist.size(); double** timeCost = new double* [n + 1]; for (int i = 0; i <= n; ++i) { timeCost[i] = new double [n + 1]; std::fill(timeCost[i], timeCost[i] + n + 1, INF); } timeCost[0][0] = 0.; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= i; ++j) { if (j != i) timeCost[i][j] = std::min(timeCost[i][j], ceil(timeCost[i - 1][j] + (double)dist[i - 1] / (double)speed - EPS)); if (j != 0) timeCost[i][j] = std::min(timeCost[i][j], timeCost[i - 1][j - 1] + (double)dist[i - 1] / (double)speed); } } for (int j = 0; j <= n; ++j) { if (timeCost[n][j] < hoursBefore + EPS) return j; } return -1; } }; ``` 时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为 $dist$ 长度。 ### 压缩DP 观察上述状态转移方程，计算 $T[i]$ 的时候只需要用到 $T[i - 1]$ 的值，所以可以去掉一个维度，复用一个长度为 $n$ 的数组即可。 为了防止状态被覆盖，遍历 $j$ 的时候要从后往前遍历。 初始值 $T[0]$ 需要单独处理。 ```c++ class Solution { public: int minSkips(std::vector<int>& dist, int speed, int hoursBefore) { const double EPS = 1e-8, INF = 1e18; const int n = dist.size(); double timeCost[n + 1]; std::fill(timeCost + 2, timeCost + n + 1, INF); timeCost[0] = ceil((double)dist[0] / (double)speed - EPS); timeCost[1] = (double)dist[0] / (double)speed; for (int i = 2; i <= n; ++i) { for (int j = i; j >= 0; --j) { if (j != i) timeCost[j] = ceil(timeCost[j] + (double)dist[i - 1] / (double)speed - EPS); if (j != 0) timeCost[j] = std::min(timeCost[j], timeCost[j - 1] + (double)dist[i - 1] / (double)speed); } } for (int j = 0; j <= n; ++j) { if (timeCost[j] < hoursBefore + EPS) return j; } return -1; } }; ``` 时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 $dist$ 长度。 最后修改：2024 年 04 月 21 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏