algorithm - Frog 用石头跳过河

Question

这与树叶在不同时间落下的经典 codility Frog-River-One 问题不同。

Problem statement

有一个地方被截断了:如果猴子可以跳过河流，函数返回0。如果不可能跳过河流，则返回-1。

一些测试用例包括:

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

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

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

图像有问题描述。我使用递归以蛮力方式完成了此操作，尽管我相信它返回了正确的答案，但它可能还不够好，因为它会产生 O(n^D) 的运行时间。

有没有办法更有效地解决这个问题？我没看到什么？我觉得可能有一个 DP 解决方案或者像一个简单的数学技巧......我附上我的解决方案以供引用。

My recursive solution with explanation

Answer 1

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

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

因此，首先有一个仅使用动态规划的简单O(ND) 解决方案。

这实际上可以减少到 O(N + D) 使用有效的算法来保持滑动窗口 [i-D .. .i](使用双端队列)