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$​ 再进行取整，就可以避免上述的误差。

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]$ 需要单独处理。

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$ 长度。