算法leetcode

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

字数统计: 1.9k字   |   阅读时长: 8分
,

摘要: 带上取整的状态转移方程

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个动态规划的问题，整体的思路上还是比较好想的。值得注意的有两个点，一个是状态转移方程中涉及到上取整操作，另一个是浮点数精度的处理问题。

题目

给你一个整数 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
2
3
4
5
n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 1e5
1 <= speed <= 1e6
1 <= hoursBefore <= 1e7

示例 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
解释：即使跳过所有的休息时间，也无法准时参加会议。

题解

算法: 动态规划

dist 中共有 n 段路，编号从 0 到 n - 1。这 n 段路最多可以跳过 n - 1 次休息，最少可以跳过零次，也就是每走完一步，都休息。

定义 $dp[i][k]$ 表示走完第 $0$ 到第 $i$ 这 $i + 1$ 段路，恰好跳过 $k$ 次休息的情况下，最少所需时间。

其中 $i$ 表示阶段，由于 dist 中的每段距离都要按顺序一步一步地走，不能跳过或返回，所以阶段的推导是线性的。

$k$ 为阶段 $i$ 的附加信息，需要满足 $0 \leq k \leq i$，于是阶段 $i$ 和附加信息 $k$ 共同构成了状态，其中第 $i$ 个阶段有 $k=0,\cdots,i$ 共 $i+1$ 个状态。

阶段 $0$ 只有一个状态 $dp[0][0] = dist[0]$，它就是初始化条件，然后我们依次推导第 $1,2,\cdots,n-1$ 阶段的状态。

这样当我们推导完所有状态之后，按顺序枚举 $k=0,1,\cdots,n-1$，考察 $dp[n-1][k]$，如果 $dp[n-1][k] \leq hoursBefore$ 则 $k$ 就是最少的跳过休息次数。

下面我们考虑状态转移方程，问题是如何从上一阶段的某些状态 $dp[i-1][..]$ 推导出当前阶段的状态 $dp[i][k]$。

$dp[i][k]$ 表示的是走完 $dist[0..i]$，它相当于先走完 $dist[0..i-1]$，然后再走 $dist[i]$，所需时间为 $t = dist[i] / speed$：

  • 如果走 $dist[i]$ 之前休息了，那么 $k$ 不变，这需要 $k < i$，于是：
  • 如果走 $dist[i]$ 之前跳过休息，$dist[0..i-1]$ 这一段的跳过休息次数就是 $k-1$，这需要 $i > 0$，于是：

综合考虑上面两种情况以及 $k$ 的取值，状态转移方程如下：

浮点数精度问题

在实现时，有两个地方涉及到浮点数精度问题：

  • 在状态转移方程的 $\left\lceil dp[i - 1][k]\right\rceil$ 这部分，可能出现类似于 $dp[i-1][k] = 7.0000001$ 的情况，这样 $\left\lceil dp[i - 1][k]\right\rceil$ 就成了 $8$，而它实际上应该是 $7$，代码写为 math.ceil(dp[i - 1][k] - EPS) 即可避免。
  • 在判断 $dp[n - 1][k] <= hoursBefore$ 时，$dp[n-1][k]$ 有可能稍微超过 $hoursBefore$，例如 $hoursBefore = 7$ 而 $dp[n-1][k]=7.0000001$，这种情况应该是判定成功的，代码写为 dp[n - 1][k] < hoursBefore + EPS 即可避免。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import math

EPS = 1e-8
INF = 1e11

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        # dp[i][k] := 走完 dist[0..i] 段路，跳过 k 次休息，最短所需时间
        # 其中 0 <= k <= i
        dp = [[INF for _ in range(n)] for _ in range(n)]
        dp[0][0] = dist[0] / speed
        for i in range(1, n):
            t = dist[i] / speed
            for k in range(i + 1):
                if k < i:
                    # 第 i - 1 段路后不跳过休息
                    dp[i][k] = min(dp[i][k], math.ceil(dp[i - 1][k] - EPS) + t)
                if k > 0:
                    # 第 i - 1 段路后跳过休息
                    dp[i][k] = min(dp[i][k], dp[i - 1][k - 1] + t)
        ans = -1
        for k in range(n):
            if dp[n - 1][k] < hoursBefore + EPS:
                ans = k
                break
        return ans

如果想避免浮点数精度方面的处理，可以吧时间放慢 speed 倍，即 dist 中的距离不变，但速度视为 1。每走一步，如果休息，则需要休息到 speed 的整数倍。

这样走一遍同样的动态规划过程，最后判断 dp[n-1][k] <= hourBefore * speed 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
INF = 1e15

def gap(x: int, p: int) -> int:
    m = x % p
    return m if m == 0 else p - m

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        dp = [[INF for _ in range(n)] for _ in range(n)]
        dp[0][0] = dist[0]
        for i in range(1, n):
            t = dist[i]
            for k in range(i + 1):
                if k < i:
                    dp[i][k] = min(dp[i][k], dp[i - 1][k] + gap(dp[i - 1][k], speed) + t)
                if 0 < k:
                    dp[i][k] = min(dp[i][k], dp[i - 1][k - 1] + t)
        ans = -1
        for k in range(n):
            if dp[n - 1][k] <= hoursBefore * speed:
                ans = k
                break
        return ans
Share