https://*.com/questions/39881068/frog-jumps-across-a-river-with-stones
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})
So first there is a simple
O(ND)
solution using only dynamic programming.This can actually be reduced to
O(N + D)
using an efficient algorithm to maintain the mininum ofshortest
on the sliding window[i-D ... i]
(using double-ended queue).