algorithm - 面试谜题: Jump Game

Question

跳跃游戏:给定一个数组，从第一个元素开始跳到最后一个。跳转长度最多可以是数组中当前位置的值。最佳结果是您以最少的跳跃次数达到目标。

找到最佳结果的算法是什么？

一个例子:给定数组A = {2,3,1,1,4}到达终点(索引列表)的可能方式是

1. 0,2,3,4(将 2 跳转到索引 2，然后将 1 跳转到索引 3，然后将 1 跳转到索引 4)
2. 0,1,4(跳转 1 到索引 1，然后跳转 3 到索引 4)

由于第二个解决方案只有 2 次跳跃，所以这是最佳结果。

Answer 1

概览

给定数组 a 和当前位置的索引 i，重复以下操作，直到到达最后一个元素。

考虑 a[i+1] 到 a[a[i] + i] 中的所有候选“跳转元素”。对于索引 e 处的每个此类元素，计算 v = a[e] + e。如果其中一个元素是最后一个元素，则跳转到最后一个元素。否则，跳转到具有最大 v 的元素。

更简单地说，在触手可及的元素中，寻找能让您在下一跳跃中走得最远的元素。我们知道这个选择 x 是正确的，因为与您可以跳转到的所有其他元素 y 相比，从 y 可到达的元素是从 x 可到达的元素的子集(向后跳转的元素除外，这显然是错误的选择)。

该算法的运行时间为 O(n)，因为每个元素只需要考虑一次(可以跳过第二次考虑的元素)。

例子

考虑值数组 a、indicies、i 以及索引和值 v 的总和。

i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
v ->  4  12   3   4   5   6   7   8   9  10  11  12  13

从索引 0 开始，考虑接下来的 4 个元素。找到具有最大 v 的那个。该元素位于索引 1，因此跳转到 1。现在考虑接下来的 11 个元素。目标触手可及，向着目标跳吧。

演示

参见 here或 here with code .