跳过数组的最快算法 [英] Fastest algorithm to hop through an array
问题描述
以正数数组A开头.从索引0开始.对于任何x< = A [i]，您都可以从索引i移至索引i + x.目标是找到到达数组末尾所需的最少移动次数.
Start with an array A of positive numbers. Start at index 0. From index i, you can move to index i+x for any x <= A[i]. The goal is to find the minimum number of moves needed to get to the end of the array.
这是一个例子:
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
如果您总是在每一步中都尽可能地走下去，那么这就是您得到的:
If you always go as far as possible in each move, then this is what you get:
0 , 2 , 3 , 5 , 7
这需要4个动作.但是通过这种方式，您可以更快地通过它
This takes 4 moves. But you can get through it faster by doing it this way
0 , 1 , 4 , 7
这只需要三步.
我考虑了一下，做了我想到的第一件事，但是经过几天的思考，我仍然不知道如何做得更好.
I thought about this for a bit and did the first thing I thought of, but after thinking for a few more days, I still don't know how to do it any better.
这是我的主意.从数组的末尾开始，并跟踪从某个位置到末尾的最小移动量.因此，对于本例， moves [7] = 0 因为已经结束了.然后 moves [6] = 1 ，因为它需要一招才能走到尽头.我的公式是
Here's my idea. Start at the end of the array and keep track of the minimum number of moves from some position to the end. So for the example, moves[7] = 0 because it's the end already. Then moves[6] = 1 because it takes one move to get to the end. My formula is
moves[i] = 1 + min(moves[i+1], moves[i+2], ... , moves[i+A[i]])
到开始的时候，我知道移动的次数.
By the time I get to the beginning, I know the number of moves.
所以这是O(n ^ 2)，我想是可以的，但是也许有更快的方法吗?
So this is O(n^2) which is okay I guess, but probably there is a faster way?
推荐答案
由于您可以在[1，A [i]]中选择任意x，所以我想有一个非常简单的解决方案:
Since you can chose any x in [1,A[i]] I guess there is a pretty simple solution :
从0开始:
选择下一个可到达的元素，从中可以到达更远的元素.即我选择的i对[1，A [i]]中的x最大化i + A [i + x]
select the next reachable element from which you can reach the farther element. i.e chose i that maximize i+A[i+x] for x in [1,A[i]]
直到您到达列表的末尾.
until you arrive at the end of the list.
示例:
{2，4，1，2，3，2，4，2}
{2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
从0开始
从0开始，您可以达到1或2:
from 0 you can get to 1 or to 2:
- 从1您可以达到4
- 从2您可以达到3
因此max(0 + A [0 + x])用于i = 1
选择1 从1到2 3 4:
- 从4您可以达到7
- 从3您可以达到5
- 从2您可以达到3
因此max(1 + A [1 + x])适用于i = 4
选择4
您可以达到7
停止
the resulting list is :
0,1,4,7
正如我的评论中所述，我认为它是O(N)，因为从i开始，您至少要进行2 * x次运算才能达到i + x + 1.
As explained in my comments I think it's O(N), because from i you reach i+x+1 in at least 2*x operations.
伪"证明
您从0开始(最佳)
然后选择最大化(0 + A [0 + x])(即最大化下一个元素的可达性)的i
then you select i that maximize(0+A[0+x]) (i.e that maximize the reachability for the next element)
从那里我可以到达从0可以到达的所有其他元素可以到达的任何其他元素(这是一个很长的句子，但这意味着:谁可以做更多的事情，可以做更少的事情，因此，如果我不是最优的，它就是最佳"
from that i you can reach any other element that is reachable from all other elements reachable from 0 (it's a long sentence, but it means : who can do more, can do less, therefore if i is not optimal,it's as good as optimal)
所以我是最佳的
然后逐步进行这种推理，证明了该方法的最优性.
then following step by step this reasoning, it proves the optimality of the method.
如果有人知道如何更数学地表述，请随时进行更新.
If someone knows how to formulate that more mathematically, feel free to update it.
这篇关于跳过数组的最快算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
