从正数数组A的索引0开始。从索引i，您可以移动到索引i+x，其中x <= A[i]。目标是找到到达数组末尾所需的最小移动次数。
以下是一个示例：
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
如果你每次都尽可能地走得更远，那么你将得到以下结果：
0 , 2 , 3 , 5 , 7
这需要4个步骤。但你可以通过以下方法更快地完成它。
0 , 1 , 4 , 7
这只需要3步。
我想了一会儿，做了我能想到的第一件事，但是思考了几天后，我仍然不知道如何更好地完成它。
以下是我的想法。从数组的末尾开始，并跟踪从某个位置到末尾的最小移动次数。所以对于这个例子，moves[7] = 0，因为它已经是末尾了。然后moves[6] = 1，因为到达末尾需要一次移动。我的公式是
moves[i] = 1 + min(moves[i+1], moves[i+2], ... , moves[i+A[i]])
当我到达开头的时候，我知道移动的次数。
所以这是O(n^2)，我猜还有更快的方法吧？
因为你可以选择任何一个x在[1,A[i]]之间,所以我猜有一个相当简单的解决方案:
从0开始：
选择下一个可达的元素，从中可以到达更远的元素。
i.e 选择i使得i+A[i+x]在[1,A[i]]内最大，其中x∈[1,A[i]]直到到达列表的结尾。
例子：
{2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
从0开始
从0可以到达1或者2:
因此max(0+A[0+x])为i=1
选择1 从1可以到达2 3 4:
因此max(1+A[1+x])为i=4
选择4
你可以到达7
停止
the resulting list is :
0,1,4,7
根据我的评论，我认为复杂度为O(N)，因为从i到i+x+1至少需要2*x步。
'伪证明'
你从0开始(这是最优的)
然后你选择i使得(0+A[0+x])最大化（即最大化下一个元素的可达性）
从i开始，你可以到达任何其他从0可达的元素（它是一个长句，但意思是：谁能做更多，就能做更少。如果i不是最优的，那么它和最优的一样好）
所以i是最优的
然后按照这个推理逐步进行，它证明了该方法的最优性。
如果有人知道如何更数学化地表述，请随意更新它。
i0 = 0
i1 = A[0]
感性部分并不太复杂：
i(k+2) = max { A_(ik+1) + ik , A_(ik+1) + ik+1, ..., A_(i(k+1)) + i(k+1) }
你可以将它表述为一个图算法（实际上，哪个问题不能呢？）。让数组中的位置成为顶点，而可能的目的地从每个顶点出发。在你的例子中，顶点0将有边到1和2，而顶点1将有边到2、3、4和5。
有几种高效的图搜索算法。例如，Dijkstra的算法是O（|E| + |V|log|V|），而A*算法是O（log h*），如果你能想出一个好的启发式算法，那么它会更好。
public static void arrayHop()
{
int[] input = { 10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1 };
int length = input.length;
int answer = calcArrayHop(input, length);
}
public static int calcArrayHop(int[] input, int length) {
int minSteps;
int[] reqSteps = new int[length];
for(int i=0;i<length;i++)
reqSteps[i]=Integer.MAX_VALUE;
int nextStep;
for (int i = length - 1; i >= 0; i--) {
int minsteps = Integer.MAX_VALUE;
if (i + input[i] >= length) {
reqSteps[i] = 1;
} else
{
for (int j = i+1; j <= (i + input[i]); j++) {
if(j>input.length-1)
break;
if (reqSteps[j] < minsteps)
minsteps = reqSteps[j];
}
reqSteps[i] = minsteps+1;
}
}
return reqSteps[0];
}
}
这是对Ricky Bobby答案的轻微修改，我将展示其优化：
find_shortest_path(A):
path := [0]
last := 0
max_reachable = 0
while A[last] + last < length(A) :
next_hop := x such that max_reachable < x <= A[last] + last and last + A[x] is maximum
push(path, x)
max_reachable = A[last] + last
last := x
return path
正确性证明： 我将使用归纳法来证明由我的算法创建的路径上的节点。
我要展示的属性是P(i) = 我的路径的第i个节点具有不小于任何最优路径的第i个节点的“可达性”
其中，可达性被定义为从该节点可以跳到的最高节点的数量，或者如果您可以越过数组的末尾，则为+无穷大
P(0)是显然的。
假设对于k >= 0，P(k)成立
现在考虑由我的算法创建的路径中的第（k + 1）个节点。由于我的算法选择了节点k，使其具有与最优路径的节点k相同的可达性，因此可能成为我的算法的第（k + 1）个节点的节点集合是任何最优路径的节点集合的超集。由于我的算法选择具有最大可达性的节点，因此P(K + 1)成立。
通过归纳法，P(k)对于所有k（直到创建的路径的大小）都成立。
由于我的算法将在到达数组末尾时结束，而且这将不会晚于任何最优路径，因此可以得出结论，我的算法创建的路径是最优的。
最优性证明： 每个数组单元格最多只被考虑一次，因此它的时间复杂度为O(n)，这是渐进最优的。我认为在每种情况下都无法设计出检查更少单元格的算法。
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
0
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
0 1 1 (num of steps)
0 0 (source)
^ (current position)
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
0 1 1 2 2 2
0 0 1 1 1
^
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
0 1 1 2 2 2
^
etc...
我的天真方法 - 从开始出发，通过所有路径进行广度优先搜索（子节点为A [i + 1] .. A [i + n]），将找到的路径保存到某个数组中，然后获取最短路径。当然，所有索引i + n> length（A）都被丢弃。因此，它的上限是O（n * min（n，max（A [i = 0..n]））+ n）-在实践中应该小于二次方。
