从正数的数组A开始.从索引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)我猜是好的,但可能有更快的方法？
Ric*_*bby 13
既然您可以选择[1,A [i]]中的任何x,我想有一个非常简单的解决方案:
从0开始:
选择下一个可到达的元素,从中可以到达更远的元素. 即选择i,使[1,A [i]]中的x最大化i + A [i + x]
直到你到达列表的末尾.
例:
{2,4,1,2,3,2,4,2}
从0开始
从0开始你可以得到1或2:
因此max(0 + A [0 + x])是i = 1
从1中选择1你可以得到2 3 4:
因此,对于i = 4,max(1 + A [1 + x])
选择4
你可以达到7
停
the resulting list is :
0,1,4,7
正如我在评论中所解释的那样,我认为它是O(N),因为从i开始,你至少在2*x操作中达到i + x + 1.
'伪'证明
你从0开始(这是最优的)
然后你选择i最大化(0 + A [0 + x])(即最大化下一个元素的可达性)
从那个你可以到达任何其他元素,可以从0到达的所有其他元素到达(这是一个长句子,但它意味着:谁可以做得更多,可以做得更少,因此,如果我不是最优,它就像最佳一样好)
所以我是最优的
然后逐步推导出这种推理,证明了该方法的最优性.
如果有人知道如何以数学方式表达,请随时更新它.
| 归档时间： |
|
| 查看次数： |
6578 次 |
| 最近记录： |