Given a set of n stones, arranged in a row at equal distances from each other. The stones are numbered from 0 to n-1. A frog that is on stone number 0 has to get to stone number n-1.
A jump is a move from stone i to stone j ( i<j ). Such a jump has length equal to j-i. The maximum jump length of the frog depends on its energy level (which cannot drop below 0). A jump of length j-i costs the frog j-i energy. For example, with an initial energy of 3, a frog on stone 0 can jump to stone 3 at most.
On some stones, there may be worms, which add energy to the frog. If the frog jumps on a stone with a worm on it, it MUST eat the worm. The list T[0...n-1] contains the energy values of the worms on the corresponding stones. If there is no worm on the stone, this is equivalent to a value of 0.
The frog starts with 0 Energy, but it is guaranteed that there is a worm on stone number 0.
Given a list T, the task is to return a list of the indexes of the stones on which the frog has been, before getting to stone n-1. However, this must be the shortest possible list. In some cases there may be more than one solution, whichever is accepted. It is guaranteed that always the frog will be able to get to stone n-1.
Example no. 1:
For T = [3, 0, 2, 1, 0, 2, 5, 0] the answer is [0, 2, 5].
Example no. 2:
For T = [7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0] the answer is [0, 3, 7] or [0, 5, 7].
I have no idea how to approach this problem, all I know is that I probably need to use some dynamic programming or greedy algorithm here, but how? Anyone have any ideas?
CodePudding user response：
Note that an optimal solution never jumps backwards: remove the jump immediately before turning backwards to make it more optimal, thus disproving the initial solution's optimality. This gives us a natural order in which to consider positions.
Consider the state of the problem's world:
- the frog is at position p,
- has e energy,
- and used k jumps to get there.
So, the trivial form of a solution is: given p, e, and k, is it possible to arrive at such a state?
Now, we can just ask f(p,e,k), which is either true or false, for every possible set of parameters, consider the previous or next jump to arrive at such a state, and perhaps get an inefficient but working solution, recursive or iterative. The base is f(0,T[0],0) = true, and the desired states are f(n-1,?,?).
To make it more efficient, perhaps we can make some of the parameters (p, e, or k) the target function.
For example, consider g(p,e) = min k: for given position and energy, calculate the minimum number of jumps to have such position and energy. For convenience, define k as plus-infinity if such state (p,e) is not reachable with any number of jumps.
Or consider h(p,k) = max e: if we reached position p in exactly k jumps, how much energy can we have left as surplus? Again, define as minus-infinity if (p,k) is not reachable at all.
Finally, we may even be able to do a(p) = best pair (k,e): for a given position p, what is the minimum number of jumps k to arrive there, and with this exact number of jumps, what is the maximum amount of surplus energy e the frog can still have? (Perhaps this won't work, but it's still educative to think why exactly it won't.)
Consider this list, or expand on it, to decide which approach would work for you -- or at all.
CodePudding user response：
How about this algorithm?
- Calculate the minimum energy required to reach the end, say
M, at each stone. - Jump to the farthest stone where you would keep at least the minimum energy required at the stone.
- Repeat step 2 until you reach the last stone.
Example 2:
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
Steps
1: Jump to 5 - energy 5
2: Jump to 7 - energy 9
3: Jump to 14