跳跃游戏:闭区间上的最小子覆盖

March 09, 2019

LeetCode 第 45 题第 55 题:一个列表中的每个数分别代表从此处能“跳跃”的最远距离,问从首位是否能够跳到末位,如果能,最少需要跳几次?

[2,3,1,1,4][2,3,1,1,4],从首位向右跳 11 个距离到第 22 个位置,再向右跳 33 个距离到达末位。

往左跳还是往右跳

首先我们排除“往左跳”的情况:

假如某一条路径中存在往左跳,我们可以替换为一条没有“往左跳”的路径:

...abc...  (a<c<b)... \rightarrow a \rightarrow b \rightarrow c \rightarrow ...~~( a \lt c \lt b )

bbcc 往左跳了,很明显,acac 之间距离小于 abab,既然从 aa 能跳到 bb,那么从 aa 也一定能跳到 cc,于是,可以去掉 bb 少跳一步:

...ac...... \rightarrow a \rightarrow c \rightarrow ...

存在性:如果从首位到末位的路径存在,那么一定存在一条只往右跳的路径;

最优解:最短路径一定只包含往右跳的路径。

题目等价于从每个位置只允许往右跳的情形。

闭区间上的闭覆盖

数轴上的 0,1,2,3,40,1,2,3,4 分别表示所处位置,每个点往右跳的范围一一对应一个闭区间:

00 ~ [0,2][0,2]11 ~ [1,4][1,4]22 ~ [2,3][2,3]33 ~ [3,4][3,4]44 ~ [4,8][4,8]

由点到闭区间的双射,构造出从一条路径到一组闭区间序列上的一个双射。

例如:

路径 0140\rightarrow 1\rightarrow 4 对应 ([0,2],[1,4])([0,2],[1,4])

路径 012340\rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 对应 ([0,2],[1,4],[2,3],[3,4])([0,2],[1,4],[2,3],[3,4])

这组闭区间序列满足条件:

  • 相邻交集不为空

  • 是一个覆盖

如果路径中存在

...ab......\rightarrow a\rightarrow b\rightarrow ...

表示 bbaa 的跳跃范围内,b[a,]b[b,][a,][a,][b,]b\in[a,\sim] \Rightarrow b \in [b,\sim]\cap [a,\sim] \Rightarrow [a,\sim] \cap [b,\sim] \neq \varnothing.

反过来,如果两个区间的交集不为空,第二个区间的起点在第一个区间之中,代表从第一个区间的起点到第二个区间起点之间存在路径。

从首位到末位存在一条路径,等价于存在满足上面两个的一组闭区间序列,最短路径时这个序列的覆盖刚好是最小子覆盖。

寻找最小子覆盖

C=[0,]\mathbb{C} = [0,\sim] 开始:

  • C\mathbb{C} 包含终点,那么构建结束。

  • 寻找左端点落在 C\mathbb{C} 中,右端点落在 C\mathbb{C} 之外的区间

    • 如果没有,那么不存在覆盖。

    • 如果有,在其中选择右端点最大的一个,把它加入 C\mathbb{C}

重复这个过程,直到 C\mathbb{C} 包含终点,即为最小子覆盖。

证明

如图中的情况,直觉上,对于 AA,下一个区间要选择右端点最大的 DD,因为其剩下的区间“最小”,如果一组区间能够覆盖选 BBCC 剩下的,那么也必然能够覆盖选 DD 剩下的。

证明此算法必然能找到一种最小子覆盖(虽然最小子覆盖可能不唯一):

我们用上面算法得到了的一个包含 aa 个闭区间的序列(其中 A0=[0,]A_0 = [0,\sim]),

(A0,A1,A2,...,Ak,Ak+1,...,Aa1)(A_0, A_1, A_2, ..., A_k, A_{k+1}, ..., A_{a-1})

它们的左端点即我们所找到的一条长度为 aa 的路径(其中 a0=0a_0 = 0),

a0a1a2...akak+1...aa1na_0\rightarrow a_1\rightarrow a_2\rightarrow ...\rightarrow a_k\rightarrow a_{k+1}\rightarrow ...\rightarrow a_{a-1}\rightarrow n

假设有一条长为 bb 的路径,它从第 kk 位起开始和上述选择不同,

a0a1a2...bkbk+1...bb1na_0\rightarrow a_1\rightarrow a_2\rightarrow ...\rightarrow b_k\rightarrow b_{k+1}\rightarrow ...\rightarrow b_{b-1}\rightarrow n

它所对应的一组闭区间为

(A0,A1,A2,...,Bk,Bk+1,...,Bb1)(A_0, A_1, A_2, ..., B_k, B_{k+1}, ..., B_{b-1})

AkA_k 是左端点落在 i=0k1Ai\cup_{i=0}^{k-1} A_i 中,右端点最大的一个,因此

(i=0k1AiBk)i=0kAi(\cup_{i=0}^{k-1} A_i \bigcup B_k) \subseteq \cup_{i=0}^k A_{i}

接下来,上式子左边新加入的 Bk+1B_{k+1},它的左端点 (i=0k1AiBk)i=0kAi\in (\cup_{i=0}^{k-1} A_i \bigcup B_k) \subseteq \cup_{i=0}^k A_{i},而所有左端点属于 i=0kAi\cup_{i=0}^k A_{i} 的区间中,Ak+1A_{k+1} 的右端点是最大的,因此

(i=0k1AiBkBk+1)i=0k+1Ai(\cup_{i=0}^{k-1} A_i \bigcup B_k \bigcup B_{k+1}) \subseteq \cup_{i=0}^{k+1} A_{i}

如果 b<ab \lt a,重复这个过程可以得到

(i=0k1Aii=ka1Bi)i=0b1Ai(\cup_{i=0}^{k-1} A_i \bigcup \cup_{i=k}^{a-1} B_i) \subseteq \cup_{i=0}^{b-1} A_{i}

既然左边都是一个覆盖,那么右边也一定是,但算法过程中在 Ab1A_{b-1} 处还有未覆盖完的部分,与此矛盾。

所以 bab \geq a,任意一条路径长度都不小于 aa.