青蛙用石头跳过河 [英] Frog jumps across a river with stones

问题描述

这与经典的青蛙河一号青蛙有不同的时间问题。

This is different from the classic codility Frog-River-One with leaves falling at different times problem.

问题陈述

其中有一部分被截断：如果猴子只能跨河跳，函数将返回0。如果不可能跨河跳，则返回-1。

There is a part where it got cut off: If the monkey can just jump across river, the function returns 0. If it's impossible to jump across river, then -1.

一些测试用例包括：

[[-1，5，-1，5，-1，10]，3]->返回5

[[-1, 5, -1, 5, -1, 10], 3] -> returns 5

[[1，-1，0，2，3，5]，3]->返回2

[[1, -1, 0, 2, 3, 5], 3] -> returns 2

[[0，0，0，0 ，0，0]，3]->返回0

[[0, 0, 0, 0, 0, 0], 3] -> returns 0

图片有问题描述。我使用递归以一种蛮力的方式做到了这一点，尽管我相信它返回了正确的答案，但是它可能还不够好，因为它会产生O（n ^ D）的运行时间。

The image has a problem description. I did this in a brute-force way using recursion, and although I believe it returned correct answers, it probably wasn't good enough because it would yield run time of O(n^D).

有没有一种方法可以更有效地解决此问题？我没看到什么？我觉得可能有一个DP解决方案，或者像是一个简单的数学技巧……我附上我的解决方案以供参考。

Is there a way to solve this problem more efficiently? What am I not seeing? I feel that there might be a DP solution or like a simple math trick... I am attaching my solution for reference.

我的解释性递归解决方案

推荐答案

请注意，最早可以达到 x = i 的时间可以由以下递归关系表示：

Note that the earliest time you can reach x = i can be expressed by the following recurrence relation:

shortest[i] = if A[i] = -1 then +inf 
              else max(A[i], min{shortest[j] | i - D <= j < i})

所以首先有一个简单的 O（ ND）仅使用动态编程的解决方案。

So first there is a simple O(ND) solution using only dynamic programming.

实际上可以减少为 O（N + D）使用高效算法在滑动窗口 [iD ... i] 最短的最小值c>（使用双端队列）。

This can actually be reduced to O(N + D) using an efficient algorithm to maintain the mininum of shortest on the sliding window [i-D ... i] (using double-ended queue).

这篇关于青蛙用石头跳过河的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！